Publication detail

Ordered Pure Multi-Pushdown Automata

MEDUNA, A. SOUKUP, O. ZEMEK, P.

Original Title

Ordered Pure Multi-Pushdown Automata

Type

journal article - other

Language

English

Original 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

Authors

MEDUNA, A.; SOUKUP, O.; ZEMEK, P.

RIV year

2015

Released

31. 12. 2015

ISBN

1896-5334

Periodical

Theoretical and Applied Informatics

Year of study

27

Number

1

State

Republic of Poland

Pages from

25

Pages to

47

Pages count

21

URL

https://journals.pan.pl/tai/135572

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"
}

Documents

meduna_Ordered Pure.pdf