Pumping Deterministic Monotone Restarting Automata and DCFL

0533617 - ÚI 2021 RIV DE eng C - Conference Paper (international conference)
Mráz, F. - Pardubská, D. - Plátek, Martin - Šíma, Jiří
Pumping Deterministic Monotone Restarting Automata and DCFL.
Proceedings of the 20th Conference Information Technologies - Applications and Theory. Aachen: Technical University & CreateSpace Independent Publishing, 2020 - (Holeňa, M.; Horváth, T.; Kelemenová, A.; Mráz, F.; Pardubská, D.; Plátek, M.; Sosík, P.), s. 51-58. CEUR Workshop Proceedings, 2718. ISSN 1613-0073.
[ITAT 2020: Information Technologies - Applications and Theory /20./. Oravská Lesná (SK), 18.09.2020-22.09.2020]
R&D Projects: GA ČR(CZ) GA19-05704S
Institutional support: RVO:67985807
Keywords : deterministic context-free language * restarting automaton * pumping
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://ceur-ws.org/Vol-2718/paper13.pdf

We introduce a new type of the deterministic monotone restarting automaton that enables new types of characterization of the class of deterministic context-free languages (DCFL) based on pumping. The characterization is obtained through new types of normalizations of deterministic monotone restarting automata. This paper is the first step to prepare notions for studying the relation between restarting automata and analog neuron automata, and for studying degrees of non-regularity of DCFL.
Permanent Link: http://hdl.handle.net/11104/0311953