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

Result code in 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>

Result on the web

<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

—

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

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

2022

Confidentiality

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

Article name in the collection

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

ISBN

—

ISSN

1613-0073

e-ISSN

1613-0073

Number of pages

11

Pages from-to

111-121

Publisher name

CEUR-WS.org

Place of publication

—

Event location

Zuberec

Event date

Sep 23, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—