# Proof of the equivalence of Muller automata and Parity (or Rabin chain) automata

Let $A$ be some finite alphabet and $\mathcal A = (Q, \delta, q_0)$ be some determinisitic finite automaton. Then $\mathcal A$ accepts infinite words $\xi \in A^{\omega}$ according to the Muller condition iff there exists some $\mathcal F \subseteq \mathcal P(Q)$ (called the table) such that $$\operatorname{Inf}_{\mathcal A}(\xi) \in \mathcal F$$ where $\operatorname{Inf}_{\mathcal A}$ denotes the states which are traversed infinitely often when $\xi$ is processed. It accepts according to the Rabin chain condition (or parity condition) if we have some $\mathcal C = \{ E_0, F_0, E_1, F_1, \ldots, E_n, F_n \} \subseteq \mathcal P(Q)$ such that $$E_0 \subseteq F_0 \subseteq E_1 \subseteq F_1 \subseteq \ldots \subseteq E_n \subseteq F_n$$ and there exists some $k \in \{1,\ldots, n \}$ with $\operatorname{Inf}_{\mathcal A}(\xi) \cap E_k = \emptyset$ and $\operatorname{Inf}_{\mathcal A}(\xi) \cap F_k \ne \emptyset$.

Now we have that:

Theorem: Every $\omega$-language acceptable by some Müller automaton is acceptable by some Rabin chain automaton and vice versa.

I have a question on the construction of a Rabin chain automaton for some Müller automaton. The proof uses a construction called the memory extension of a given Müller automaton $\mathcal A = (Q, \delta, q_0)$ with table $\mathcal F$. An arrangement of some symbols is a sequence or word such that every symbol occurs at most once, then let $S = \{ (u,v) \mid uv \mbox{ is an arrangement of } Q\}$ be the arrangements of $Q$ with an additional mark in between, which marks the previous position of the last state. The empty sequence is denotes by $\varepsilon$. Then build the automaton $\mathcal B = (S, \mu, (\varepsilon, i))$ with $$\mu((u,v), a) := \left\{ \begin{array}{ll} (x, yq) & \mbox{ if } uv = xqy \\ (uv, q) & \mbox{ if } q \notin uv. \end{array}\right.$$

A crucial property of the memory extension is the following:

Property: If $\mathcal A$ is an automaton and $\mathcal B$ its memory extension and $c$ is an initial path in $\mathcal A$ and $c'$ its corresponding path in $\mathcal B$. Then $T = \mbox{Inf}_{\mathcal A}(c)$ if and only if all states $(u,v) \in \mbox{Inf}_{\mathcal B}(c')$ satisfy $\underline{v} \subseteq T$ and at least one satisfies $\underline v = T$; where $\underline v$ denotes the symbols occuring in the sequence/word $v$.

Now with this, given some Müller automaton $\mathcal A = (Q, \delta, i)$ with table $\mathcal F$, we build its memory extension $\mathcal B = (S, \mu, (\varepsilon, i))$ and define the following chain $E_0 \subseteq F_0 \subseteq \ldots \subseteq E_n \subseteq F_n \ldots$. For $i \ge 0$ let $E_i$ be the set of states $(u,v)$ of $\mathcal B$ such that either $|u| < i$ or $|u| = i$ and $\underline v \notin \mathcal F$. And let $F_i$ be the union of $E_i$ and the set of states $(u,v)$ such that $|u| = i$ and $\underline v \in \mathcal F$. Then with this chain $\mathcal B$ accepts the same $\omega$-language as $\mathcal A$.

I do not understand that $\mathcal A$ with $\mathcal F$ and $\mathcal B$ with the constructed chain accept the same $\omega$-language?

The notions are from this book.

Some thoughts of me, but I am not sure about them as they seem to use properties not mentioned in the book. If $\xi$ is accepted by the Müller automaton with $T := \operatorname{Inf}_{\mathcal A}(\xi)$, then by the property we have some $(u,v) \in \mbox{Inf}_{\mathcal B}(\xi)$ such that $\underline v = T$. Set $k := |u|$, then $(u,v) \in F_k$. We have to show that $\operatorname{Inf}_{\mathcal B}(\xi) \cap E_k = \emptyset$. I assume that we have two properties of the states in $\mbox{Inf}_{\mathcal B}(\xi)$, namely

• $|uv|$ is the same for all $(u,v) \in \mbox{Inf}_{\mathcal B}(\xi)$,
• if $(u,v), (u,v') \in \mbox{Inf}_{\mathcal B}(\xi)$ then $\underline u = \underline v'$

so that if $(u', v') \in \mbox{Inf}_{\mathcal B}(\xi)$ with $|u'| < i$ we have $|v'| > |v|$ and this contradicts $\underline v' \subseteq \underline v = T$, further if $|u'| = i$ then as $\underline v' \subseteq T$ we have $\underline v' = \underline v$ as $|v'| = |v|$. This gives $E_k \cap \mbox{Inf}_{\mathcal B}(\xi) = \emptyset$.

Conversely if there exists some $\xi$ and $k$ with $\mbox{Inf}_{\mathcal B}(\xi) \cap E_k = \emptyset$ and $\mbox{Inf}_{\mathcal B}(\xi) \cap F_k \ne \emptyset$, then we have to show that for $T := \mbox{Inf}_{\mathcal A}(\xi)$ we have $T \in \mathcal F$. By the last equation we have $(u,v) \in \mbox{Inf}_{\mathcal B}(\xi)$ with $|u| = k$ and $\underline v =: S \in \mathcal F$. Further by the property some $(u',v')$ satisfies $\underline v' = T$ and $S \subseteq T$. As $\mbox{Inf}_{\mathcal B}(\xi) \cap E_k = \emptyset$ we have for all $(u'', v'') \in \mbox{Inf}_{\mathcal B}(\xi)$ that $|u''| \ge k$, and if $|u''| = k$ this implies $\underline v'' \in \mathcal F$. As $|uv| = |u'v'|$ this gives directly $S = T$.