Deep Pushdown Automata

Czech title

Hluboké zasobníkové automaty

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)

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

BibTeX

@article{BUT45075,
  author="Alexandr {Meduna}",
  title="Deep Pushdown Automata",
  journal="Acta Informatica",
  year="2006",
  volume="2006",
  number="98",
  pages="114--124",
  issn="0001-5903"
}