Dirk Nowotka and Jiri Srba
Height-Deterministic Pushdown Automata
Mathematical Foundations of Computer Science (MFCS), Český Krumlov, 2007, volume 4708 of Lecture Notes in Computer Science, pages 125-134, Springer-Verlag, Berlin, 2007.

Abstract

Pushdown automata whose stack length on every run is the same for the same input are called height-deterministic. We consider subclasses of context-free languages that are larger than the class of regular languages and still closed under boolean operations. Several of such language classes have been described in the literature. Here, we suggest a natural and intuitive model that subsumes the formalisms proposed so far by employing height-deterministic pushdown automata. Complexity questions are also considered.

Keywords: pushdown automata, height determinism, contextfree languages, boolean operations

Full paper: [ps - 399 KB] [ps.gz - 179 KB] [pdf - 223 KB].