Publication Details

Ordered Pure Multi-Pushdown Automata

MEDUNA, A.; SOUKUP, O.; ZEMEK, P. Ordered Pure Multi-Pushdown Automata. Theoretical and Applied Informatics, 2015, vol. 27, no. 1, p. 25-47. ISSN: 1896-5334.
Czech title
Uspořádané Čisté Vícezásobníkové Automaty
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Soukup Ondřej, Ing., Ph.D.
Zemek Petr, Ing., Ph.D.
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{BUT130904,
  author="Alexandr {Meduna} and Ondřej {Soukup} and Petr {Zemek}",
  title="Ordered Pure Multi-Pushdown Automata",
  journal="Theoretical and Applied Informatics",
  year="2015",
  volume="27",
  number="1",
  pages="25--47",
  doi="10.20904/271025",
  issn="1896-5334",
  url="https://journals.pan.pl/tai/135572"
}
Back to top