Typeness for \omega-Regular Automata
======================================

We introduce and study three notions of typeness for automata on
infinite words. For an acceptance-condition class \gamma (that is,
\gamma is weak, Buchi, co-Buchi, Rabin, or Streett), deterministic
\gamma-typeness asks for the existence of an equivalent
\gamma-automaton on the same deterministic structure,
nondeterministic \gamma-typeness asks for the existence of an
equivalent \gamma-automaton on the same structure, and
\gamma-powerset-typeness asks for the existence of an equivalent
\gamma-automaton on the (deterministic) powerset structure -- one
obtained by applying the subset construction.  The notions are helpful
in studying the complexity and complication of translations between
the various classes of automata. For example, we prove that
deterministic Buchi automata are co-Buchi type; it follows that a
translation from deterministic Buchi to deterministic co-Buchi
automata, when exists, involves no blow up. On the other hand, we
prove that nondeterministic Buchi automata are not co-Buchi type; it
follows that a translation from a nondeterministic Buchi to
nondeterministic co-Buchi automata, when exists, should be more
complicated than just redefining the acceptance condition. As a third
example, by proving that nondeterministic co-Buchi automata are
Buchi-powerset type, we show that a translation of nondeterministic
co-Buchi to deterministic Buchi automata, when exists, can be done
applying the subset construction. We give a complete picture of
typeness for the weak, Buchi, co-Buchi, Rabin, and Streett acceptance
conditions, and discuss its usefulness.