Decision Problems for Deterministic Pushdown Automata on Infinite Words

Christof Löding

The article surveys some decidability results for DPDAs on infinite words (omega-DPDA). We summarize some recent results on the decidability of the regularity and the equivalence problem for the class of weak omega-DPDAs. Furthermore, we present some new results on the parity index problem for omega-DPDAs. For the specification of a parity condition, the states of the omega-DPDA are assigned priorities (natural numbers), and a run is accepting if the highest priority that appears infinitely often during a run is even. The basic simplification question asks whether one can determine the minimal number of priorities that are needed to accept the language of a given omega-DPDA. We provide some decidability results on variations of this question for some classes of omega-DPDAs.

Invited Presentation in Zoltán Ésik and Zoltán Fülöp: Proceedings 14th International Conference on Automata and Formal Languages (AFL 2014), Szeged, Hungary, May 27-29, 2014, Electronic Proceedings in Theoretical Computer Science 151, pp. 55–73.
Published: 21st May 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.151.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org