Publication Details
Deep Pushdown Automata
pushdown automata
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.
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.
@article{BUT45075,
author="Alexandr {Meduna}",
title="Deep Pushdown Automata",
journal="Acta Informatica",
year="2006",
volume="2006",
number="98",
pages="114--124",
issn="0001-5903"
}