Extension Acceptance and Regular ω-Languages

We introduce a new acceptance type for regular \omega-languages, called extension acceptance, which unifies all classical acceptance conditions. We show that extension acceptance has several advantages over other acceptance conditions: 1) All classical acceptance types for regular \omega-languages, like Rabin and Muller acceptance, can be translated into extension acceptance in polynomial time and they can be seen as simple restriction of extension acceptance. 2) Boolean operations on deterministic extension automata (DEA) cause only polynomial blowup. 3) Emptiness and other decision problems for DEAs can be decided in polynomial time. 4) An extension condition is easy to specify and it can be decided in polynomial time whether a given tuple is an extension condition. Further, extension acceptance is tightly connected to the Wagner hierarchy and to Zielonka trees.

Authors

• Christopher Hugenroth

Keywords

No keywords are indexed for this paper.