Publication Details

On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops

MASOPUST, T.; MEDUNA, A. On Pure Multi-Pushdown Automata that Perform Complete Pushdown Pops. Acta Cybernetica, 2009, vol. 19, no. 2, p. 537-552. ISSN: 0324-721X.

Czech title

O čistých multi-zásobníkových automatech, které provádí úplný zásobníkový pop

Type

journal article

Language

English

Authors

Masopust Tomáš, doc. RNDr., Ph.D. (CM-SFE)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)

Keywords

Pure multi-pushdown automaton, complete pushdown pop, infinite hierarchy.

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.

Published

2009

Pages

537–552

Journal

Acta Cybernetica, vol. 19, no. 2, ISSN 0324-721X

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