2014/05/22 by Christof Löding
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.151.4
published as EPTCS 151, 2014, pp. 55-73 · In Proceedings AFL 2014, arXiv:1405.5272
arxiv created 2014/05/22 · arxiv updated 2014/05/23
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.