TY - GEN
T1 - Height-Deterministic Pushdown Automata
AU - Nowotka, Dirk
AU - Srba, Jiri
N1 - Conference code: 32
PY - 2007
Y1 - 2007
N2 - We define the notion of height-deterministic pushdown automata, a model where for any given input string the stack heights during any (nondeterministic) computation on the input are a priori fixed. Different subclasses of height-deterministic pushdown automata, strictly containing the class of regular languages and still closed under boolean language operations, are considered. Several of such language classes have been described in the literature. Here, we suggest a natural and intuitive model that subsumes all the formalisms proposed so far by employing height-deterministic pushdown automata. Decidability and complexity questions are also considered.
AB - We define the notion of height-deterministic pushdown automata, a model where for any given input string the stack heights during any (nondeterministic) computation on the input are a priori fixed. Different subclasses of height-deterministic pushdown automata, strictly containing the class of regular languages and still closed under boolean language operations, are considered. Several of such language classes have been described in the literature. Here, we suggest a natural and intuitive model that subsumes all the formalisms proposed so far by employing height-deterministic pushdown automata. Decidability and complexity questions are also considered.
KW - visibly pushdown automata
KW - deterministic context-free languages
KW - closure properties
M3 - Article in proceeding
VL - LNCS
SP - 125
EP - 134
BT - 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07), LNCS
PB - Springer
T2 - 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)
Y2 - 27 August 2007 through 31 August 2007
ER -