Two-Dimensional Rank-Reducing Grammars and Their Complexity

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Two-Dimensional Rank-Reducing Grammars and Their Complexity
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA19-21198S" target="_blank" >GA19-21198S: Complex prediction models and their learning from weakly annotated data</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)