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

Peer-reviewed article not indexed in WoS or Scopus

Original Abstract

This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete pushdown pops. This means that during a pop operation, the entire pushdown is compared with a prefix of the input, and if they match, the whole contents of the pushdown is erased 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. In addition, this paper discusses some other extensions of these automata with respect to operations they can perform with their pushdowns. More specifically, it discusses pure multi-pushdown automata that perform complete pushdown pops that are allowed to join two pushdowns and/or create a new pushdown.

English abstract

This paper introduces and discusses pure multi-pushdown automata that remove symbols from their pushdowns only by performing complete pushdown pops. This means that during a pop operation, the entire pushdown is compared with a prefix of the input, and if they match, the whole contents of the pushdown is erased 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. In addition, this paper discusses some other extensions of these automata with respect to operations they can perform with their pushdowns. More specifically, it discusses pure multi-pushdown automata that perform complete pushdown pops that are allowed to join two pushdowns and/or create a new pushdown.

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

15.12.2009

ISBN

0324-721X

Periodical

Acta Cybernetica

Volume

19

Number

2

State

Hungary

Pages from

537

Pages to

552

Pages count

16

BibTex

@article{BUT49617,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops",
  journal="Acta Cybernetica",
  year="2009",
  volume="19",
  number="2",
  pages="537--552",
  issn="0324-721X"
}