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"
}
Files
Back to top