Determinization Complexities of ω AutomataI

Complementation and determinization are two fundamental notions in automata the-ory. The close relationship between the two has been well observed in the literature. In the case of nondeterministic finite automata on finite words (NFA), complemen-tation and determinization have the same state complexity, namely Θ(2n) where n is the state size. The same similarity between determinization and complementation was found for Büchi automata, where both operations were shown to have 2Θ(n lgn) state complexity. An intriguing question is whether there exists a type of ω-automata whose determinization is considerably harder than its complementation. In this pa-per, we show that for all common types of ω-automata, the determinization problem has the same state complexity as the corresponding complementation problem at the granularity of 2Θ(·)