On Pumping RP-automata Controlled by Complete LRG(cent,$)-grammars
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10456357" target="_blank" >RIV/00216208:11320/22:10456357 - isvavai.cz</a>
Výsledek na webu
<a href="https://ceur-ws.org/Vol-3226/paper13.pdf" target="_blank" >https://ceur-ws.org/Vol-3226/paper13.pdf</a>
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Pumping RP-automata Controlled by Complete LRG(cent,$)-grammars
Popis výsledku v původním jazyce
We introduce complete LR(0)-grammars with sentinels (called complete LR(c,$)-grammars) to prepare tools for the study of pumping restarting automata controlled by this type of grammars. A complete LR(c,$)-grammar generates both a language and the complement of the language with sentinels. Based on a complete LR(c,$)-grammar, we can construct a deterministic pumping restarting automaton performing pumping analysis by reduction on each word over its input alphabet. A pumping reduction analysis is a method where an input word is stepwise simplified by removing at most two continuous parts of the current word in a way that preserves (in)correctness of the word. Each such simplification corresponds to removing parts of the current word that could be "pumped" in the sense of a pumping lemma for context-free languages. The computation of a pumping restarting automaton ends when the original word is shortened under a given length, and then it is decided about the correctness or incorrectness of the original input word. This means that pumping restarting automata can analyze both correct and incorrect inputs with respect to a deterministic context-free language (DCFL). That gives an excellent formal basis for the error localization and the error recovery of DCFL.
Název v anglickém jazyce
On Pumping RP-automata Controlled by Complete LRG(cent,$)-grammars
Popis výsledku anglicky
We introduce complete LR(0)-grammars with sentinels (called complete LR(c,$)-grammars) to prepare tools for the study of pumping restarting automata controlled by this type of grammars. A complete LR(c,$)-grammar generates both a language and the complement of the language with sentinels. Based on a complete LR(c,$)-grammar, we can construct a deterministic pumping restarting automaton performing pumping analysis by reduction on each word over its input alphabet. A pumping reduction analysis is a method where an input word is stepwise simplified by removing at most two continuous parts of the current word in a way that preserves (in)correctness of the word. Each such simplification corresponds to removing parts of the current word that could be "pumped" in the sense of a pumping lemma for context-free languages. The computation of a pumping restarting automaton ends when the original word is shortened under a given length, and then it is decided about the correctness or incorrectness of the original input word. This means that pumping restarting automata can analyze both correct and incorrect inputs with respect to a deterministic context-free language (DCFL). That gives an excellent formal basis for the error localization and the error recovery of DCFL.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2022
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of the 22nd Conference Information Technologies - Applications and Theory (ITAT 2022), Zuberec, Slovakia, September 23-27, 2022
ISBN
—
ISSN
1613-0073
e-ISSN
—
Počet stran výsledku
11
Strana od-do
111-121
Název nakladatele
CEUR-WS.org
Místo vydání
Neuveden
Místo konání akce
Zuberec, Slovensko
Datum konání akce
23. 9. 2022
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—