an element of α(β1 ... βn)ω. Conversely, suppose w ∈ α(β1 ... βn)ω. Due to definition of α, there is an initial segment of w that is an element of α and thus leads A to the state q1. From there on, the run never assumes a state outside of {q1, ... ,qn}, due to the definitions of the β's, and all the states in the set are repeated infinitely often. Therefore, A accepts the word w. Constructing a deterministic Muller automaton from a given ω-regular language The other direction of the theorem can be proven by showing that there exists a deterministic Muller automaton that recognizes a given ω-regular language. The union of finitely many deterministic Muller automata can be easily constructed; therefore without loss of generality we assume that the given ω-regular language is of the form αβω. Consider an ω-word w=a1a2... ∈ αβω. Let w(i,j) be the finite segment ai+1,...,aj-1aj of w. For building a Muller automaton for αβω, we introduce the following two concepts with respect to w. Favor A time j favors time i if j > i, w(0,i) ∈ αβ*, and w(i,j) ∈ β*. Equivalence E(i,j,k), or i is equivalent to j as judged at time k, if i,j ≤ k, w(0,i) ∈ αβ*,w(0,j) ∈ αβ*, and for every word x in Σ*, w(i,k)x ∈ β* if and only if w(j,k)x ∈ β*. It is easy to note that if E(i,j,k) then for all k < l, E(i,j,l). In other words, if i and j are ever judged to be equivalent then they will stay equivalent thereafter. And also for the same l, l favors i if and only if l favors j. Let E(i,j) if there exists a k such that E(i,j,k). Let p be the number of states in the minimum deterministic finite automaton Aβ* to recognize language β*. Now we prove two lemmas about the above two concepts. Lemma 1 For any time k, among the times i,j < k such that w(0,i) and w(0,j) ∈ αβ*, the number of equivalence classes induced by E(i,j,k) is bounded by p. Also the number of equivalence classes induced by E(i,j) is bounded by p. Proof: The finite automaton Aβ* is minimum; therefore it does not contain equivalent states. Let i and j be such that w(0,i) and w(0,j) ∈ αβ* and E(i,j,k). Then, words w(i,k) and w(j,k) will have to take Aβ* to