Height-Deterministic Pushdown Automata

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	NOWOTKA Dirk SRBA Jiří
Year of publication	2007
Type	Article in Proceedings
Conference	32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07)
MU Faculty or unit	Faculty of Informatics
Citation
Field	Informatics
Keywords	pushdown automata - visibly pushdown laguages - height determinism
Description	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.
Related projects:	Institute for Theoretical Computer Science Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing