Height-Deterministic Pushdown Automata.

Tools

Nowotka, Dirk and Srba, Jiří (2007) Height-Deterministic Pushdown Automata. [Paper] In: Mathematical Foundations of Computer Science (MFCS). , 26 - 31 Aug 2007, Cesky Krumlov, Czech Republic . Mathematical Foundations of Computer Science 2007. ; pp. 125-134 . DOI 10.1007/978-3-540-74456-6_13. Lecture Notes in Computer Science .

[thumbnail of Hpda.pdf]
Preview
 Text
Hpda.pdf
Download (228kB) | Preview

Supplementary data:

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.

Document Type: Conference or Workshop Item (Paper)
Keywords: pushdown automata hight determinism boolean closure
Research affiliation: Kiel University
Publisher: Springer
Date Deposited: 15 Feb 2013 21:23
Last Modified: 23 Sep 2019 18:01
URI: https://oceanrep.geomar.de/id/eprint/20534

Actions (login required)

View Item View Item