Publication Details

Ordered Pure Multi-Pushdown Automata

MEDUNA Alexander, SOUKUP Ondřej and ZEMEK Petr. Ordered Pure Multi-Pushdown Automata. Theoretical and Applied Informatics, vol. 27, no. 1, 2015, pp. 25-47. ISSN 1896-5334. Available from: https://journals.pan.pl/tai/135572
Czech title
Uspořádané Čisté Vícezásobníkové Automaty
Type
journal article
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Soukup Ondřej, Ing. (DIFS FIT BUT)
Zemek Petr, Ing. (DIFS FIT BUT)
URL
Keywords

pure multi-pushdown automata, total orders, accepting power

Abstract

In the presented paper we discuss pure versions of pushdown automata that have no extra non-input symbols. More specifically, we study pure multi-pushdown automata, which have several pushdown lists. We restrict these automata by the total orders defined over their pushdowns or alphabets and determine the accepting power of the automata restricted in this way. Moreover, we explain the significance of the achieved results and relate them to some other results in the automata theory.

Published
2015
Pages
25-47
Journal
Theoretical and Applied Informatics, vol. 27, no. 1, ISSN 1896-5334
DOI
10.20904/271025
BibTeX 
@ARTICLE{FITPUB10753,
   author = "Alexander Meduna and Ond\v{r}ej Soukup and Petr Zemek",
   title = "Ordered Pure Multi-Pushdown Automata",
   pages = "25--47",
   journal = "Theoretical and Applied Informatics",
   volume = 27,
   number = 1,
   year = 2015,
   ISSN = "1896-5334",
   doi = "10.20904/271025",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10753"
}
Back to top