Two-Dimensional Rank-Reducing Grammars and Their Complexity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00367678" target="_blank" >RIV/68407700:21230/23:00367678 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.25596/jalc-2023-143" target="_blank" >https://doi.org/10.25596/jalc-2023-143</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.25596/jalc-2023-143" target="_blank" >10.25596/jalc-2023-143</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Two-Dimensional Rank-Reducing Grammars and Their Complexity

Popis výsledku v původním jazyce

We study properties of a two-dimensional grammar introduced recently for use in document analysis and recognition. The grammar is obtained from the two-dimensional context-free grammar by limiting the form of productions. Variants (ranks) of the grammar with regard to productions complexity are defined. If the grammar is restricted to produce one-row pictures only, it generates regular languages. We suggest that the lowest-rank variant can be considered as a natural generalization of the regular matrix grammar, which in addition shares some of its good properties. Namely, it can be parsed in time linear in the input area and the emptiness problem is still decidable for the grammar. However, we also show that the higher-rank variants do not loosen complexity of the context-free grammar too much. There is a conditional lower bound preventing to propose a linear-time parsing algorithm. Moreover, the grammar is able to simulate the 2-counter Minsky machine, which results in non-recursive trade-offs between grammars of different ranks and also in undecidability of the emptiness problem.

Název v anglickém jazyce

Two-Dimensional Rank-Reducing Grammars and Their Complexity

Popis výsledku anglicky

We study properties of a two-dimensional grammar introduced recently for use in document analysis and recognition. The grammar is obtained from the two-dimensional context-free grammar by limiting the form of productions. Variants (ranks) of the grammar with regard to productions complexity are defined. If the grammar is restricted to produce one-row pictures only, it generates regular languages. We suggest that the lowest-rank variant can be considered as a natural generalization of the regular matrix grammar, which in addition shares some of its good properties. Namely, it can be parsed in time linear in the input area and the emptiness problem is still decidable for the grammar. However, we also show that the higher-rank variants do not loosen complexity of the context-free grammar too much. There is a conditional lower bound preventing to propose a linear-time parsing algorithm. Moreover, the grammar is able to simulate the 2-counter Minsky machine, which results in non-recursive trade-offs between grammars of different ranks and also in undecidability of the emptiness problem.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-21198S" target="_blank" >GA19-21198S: Složité predikční modely a jejich učení z částečně anotovaných dat</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Automata, Languages and Combinatorics

ISSN

1430-189X

e-ISSN

2567-3785

Svazek periodika

28

Číslo periodika v rámci svazku

1-3

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

24

Strana od-do

143-166

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85167441024