Simplification Problems for Deterministic Pushdown Automata on Infinite Words

摘要

The article surveys some decidability results concerning simplification problems for DP-DAs 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.