One-Side Pumping and Two-Side Pumping by Complete CF(¢, $)-grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00369658" target="_blank" >RIV/68407700:21230/23:00369658 - isvavai.cz</a>
Alternative codes found
RIV/00216208:11320/23:10477033
Result on the web
<a href="https://ceur-ws.org/Vol-3498/paper14.pdf" target="_blank" >https://ceur-ws.org/Vol-3498/paper14.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
One-Side Pumping and Two-Side Pumping by Complete CF(¢, $)-grammars
Original language description
We introduce context-free grammar with sentinels, CF(¢, $)-grammar, as a generalization of recently introduced LR(¢, $)grammar. Original LR(¢, $)-grammars can be used to construct deterministic pumping restarting automata performing correctness and error preserving pumping analysis by reduction on each word over its input alphabet. Pumping analysis by reduction involves step-wise simplification of an input word by removing at most two continuous parts of the current word while preserving the correctness or incorrectness of the word. Each such simplification step corresponds to removing portions of the current word that can be “pumped” according to the pumping lemma for context-free languages, and thus, it does not use any nonterminals. One-side pumping grammars are CF(¢, $)-grammars that allow removing just one continuous part in each step of pumping reduction. A complete CF(¢, $)-grammar generates both a language and its complement with sentinels. We show that complete one-side pumping CF(¢, $)-grammars characterize the class of regular languages, while LR(¢, $)-grammars that allow two-side pumping reductions characterize the class of deterministic context-free languages. LR(¢, $)-grammars that do not allow any one-side pumping reduction generate non-regular languages only.
Czech name
—
Czech description
—
Classification
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)
Result continuities
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)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 23rd Conference Information Technologies – Applications and Theory (ITAT 2023)
ISBN
—
ISSN
1613-0073
e-ISSN
1613-0073
Number of pages
11
Pages from-to
110-120
Publisher name
CEUR Workshop Proceedings
Place of publication
Aachen
Event location
Tatranské Matliare
Event date
Sep 22, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—