@article{doi:10.1142/S0129054115400122,
    Abstract = {The article surveys some decidability results concerning simplification problems for DPDAs on infinite words ({$\omega$}-DPDAs). We summarize some recent results on the regularity problem, which asks for a given {$\omega$}-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 {$\omega$}-DPDA. 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.},
    Author = {L{\"o}ding, Christof},
    EPrint = {https://doi.org/10.1142/S0129054115400122},
    Journal = {International Journal of Foundations of Computer Science},
    Number = {08},
    Pages = {1041-1068},
    Title = {Simplification Problems for Deterministic Pushdown Automata on Infinite Words},
    URL = {https://doi.org/10.1142/S0129054115400122},
    Volume = {26},
    Year = {2015},
    bdsk-url-1 = {https://doi.org/10.1142/S0129054115400122},
    date-added = {2020-08-12 12:03:47 +0200},
    date-modified = {2020-08-12 12:03:47 +0200},
    doi = {10.1142/S0129054115400122}
}

@article{doi:10.1142/S0129054115400122, Abstract = {The article surveys some decidability results concerning simplification problems for DPDAs on infinite words ({$\omega$}-DPDAs). We summarize some recent results on the regularity problem, which asks for a given {$\omega$}-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 {$\omega$}-DPDA. 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.}, Author = {L{\"o}ding, Christof}, EPrint = {https://doi.org/10.1142/S0129054115400122}, Journal = {International Journal of Foundations of Computer Science}, Number = {08}, Pages = {1041-1068}, Title = {Simplification Problems for Deterministic Pushdown Automata on Infinite Words}, URL = {https://doi.org/10.1142/S0129054115400122}, Volume = {26}, Year = {2015}, bdsk-url-1 = {https://doi.org/10.1142/S0129054115400122}, date-added = {2020-08-12 12:03:47 +0200}, date-modified = {2020-08-12 12:03:47 +0200}, doi = {10.1142/S0129054115400122} }