Back to Search
Start Over
Simplification Problems for Deterministic Pushdown Automata on Infinite Words.
- Source :
-
International Journal of Foundations of Computer Science . Dec2015, Vol. 26 Issue 8, p1041-1068. 28p. - Publication Year :
- 2015
-
Abstract
- The article surveys some decidability results concerning simplification problems for DPDAs on infinite words ( ω-DPDAs). We summarize some recent results on the regularity problem, which asks for a given ω-DPDA, whether its language can also be accepted by a finite automaton. The results also give some insights on the equivalence problem for a subclass of ω-DPDA. Furthermore, we present some new results on the parity index problem for ω-DPDAs. For the specification of a parity condition, the states of the ω-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 ω-DPDA. We provide some decidability results on variations of this question for some classes of ω-DPDAs. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 26
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 113271649
- Full Text :
- https://doi.org/10.1142/S0129054115400122