Result 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.
Type
journal article
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Soukup Ondřej, Ing., Ph.D., DIFS (FIT)
Zemek Petr, Ing., Ph.D.
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.

Keywords

pure multi-pushdown automata, total orders, accepting power

URL
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
Projects
Advanced recognition and presentation of multimedia data, BUT, Vnitřní projekty VUT, FIT-S-11-2, start: 2011-01-01, end: 2013-12-31, completed
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, start: 2011-01-01, end: 2015-12-31, completed
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
V3C - Visual Computing Competence Center, TAČR, Centra kompetence, TE01020415, start: 2012-05-01, end: 2019-12-31, completed
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top