Publication Details

Deep Pushdown Automata

MEDUNA Alexander. Deep Pushdown Automata. Acta Informatica, vol. 2006, no. 98, pp. 114-124. ISSN 0001-5903.
Czech title
Hluboké zasobníkové automaty
Type
journal article
Language
english
Authors
Keywords

pushdown automata

Abstract

This paper introduces and discusses deep pushdown automata as a generalization of the classical pushdown automata. This generalization consists in allowing them to make expansions deeper in the pushdown.

Annotation

This paper introduces and discusses deep pushdown automata as a generalization of the classical pushdown automata. This generalization consists in allowing them to make expansions deeper in the pushdown. Based on the expansion depth, the present paper establishes an infinite hierarchy of language families that coincides with the hierarchy resulting from the n-limited state grammars, so the deep pushdown automata actually represent the automaton counterpart to these grammars. In its conclusion, this paper suggests some open problem areas.

Published
2006
Pages
114-124
Journal
Acta Informatica, vol. 2006, no. 98, ISSN 0001-5903
Book
Acta Informatica
Publisher
Springer Verlag
Place
Maraburg, DE
BibTeX
@ARTICLE{FITPUB8000,
   author = "Alexander Meduna",
   title = "Deep Pushdown Automata",
   pages = "114--124",
   booktitle = "Acta Informatica",
   journal = "Acta Informatica",
   volume = 2006,
   number = 98,
   year = 2006,
   location = "Maraburg, DE",
   publisher = "Springer Verlag",
   ISSN = "0001-5903",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8000"
}
Back to top