On Pumping RP-automata Controlled by Complete LR(¢, $)-grammars

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00362453" target="_blank" >RIV/68407700:21230/22:00362453 - isvavai.cz</a>

Výsledek na webu

<a href="http://ceur-ws.org/Vol-3226/paper13.pdf" target="_blank" >http://ceur-ws.org/Vol-3226/paper13.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On Pumping RP-automata Controlled by Complete LR(¢, $)-grammars

Popis výsledku v původním jazyce

We introduce complete LR(0)-grammars with sentinels (called complete LR(¢,$)-grammars) to prepare tools for the study of pumping restarting automata controlled by this type of grammars. A complete LR(¢,$)-grammar generates both a language and the complement of the language with sentinels. Based on a complete LR(¢,$)- 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 LR(¢, $)-grammars

Popis výsledku anglicky

We introduce complete LR(0)-grammars with sentinels (called complete LR(¢,$)-grammars) to prepare tools for the study of pumping restarting automata controlled by this type of grammars. A complete LR(¢,$)-grammar generates both a language and the complement of the language with sentinels. Based on a complete LR(¢,$)- 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.

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)

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í

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ů

Název statě ve sborníku

Proceedings of the 22nd Conference Information Technologies – Applications and Theory (ITAT 2022)

ISBN

—

ISSN

1613-0073

e-ISSN

1613-0073

Počet stran výsledku

11

Strana od-do

111-121

Název nakladatele

CEUR-WS.org

Místo vydání

—

Místo konání akce

Zuberec

Datum konání akce

23. 9. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—