Publication result detail

On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops

MASOPUST, T.; MEDUNA, A.

Original Title

On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops

English Title

On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, the pushdown is completely emptied and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simple matrix grammars. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns.

English abstract

This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete-pushdown pops. During this operation, the entire pushdown is compared with a prefix of the input, and if they match, the pushdown is completely emptied and the input is advanced by the prefix. The paper proves that these automata define an infinite hierarchy of language families identical with the infinite hierarchy of language families resulting from right linear simple matrix grammars. If these automata are allowed to join their pushdowns and create new pushdowns, then they define another infinite hierarchy of language families according to the number of pushdowns.

Keywords

pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy

Key words in English

pure multi-pushdown automaton, complete-pushdown pop, infinite hierarchy

Authors

MASOPUST, T.; MEDUNA, A.

RIV year

2010

Released

27.05.2008

Publisher

Computer and Automation Research Institute, Hungarian Academy of Sciences

Location

Balatonfured

ISBN

978-963-311-367-7

Book

Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings

Pages from

325

Pages to

336

Pages count

12

BibTex

@inproceedings{BUT27768,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Pure Multi-Pushdown Automata that Perform Complete-Pushdown Pops",
  booktitle="Automata and Formal Languages. The 12th International Conference, AFL 2008, Balatonfured, Hungary, May 27-30, 2008, Proceedings",
  year="2008",
  pages="325--336",
  publisher="Computer and Automation Research Institute, Hungarian Academy of Sciences",
  address="Balatonfured",
  isbn="978-963-311-367-7"
}