Pumping Deterministic Monotone Restarting Automata and DCFL

0533617 - ÚI 2021 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
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]
Grant CEP: GA ČR(CZ) GA19-05704S
Institucionální podpora: RVO:67985807
Klíčová slova: deterministic context-free language * restarting automaton * pumping
Obor OECD: 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.
Trvalý link: http://hdl.handle.net/11104/0311953