Automata

Consider the example in the last proof: We showed that there is no DBW of the language consisting of words with finitely many zeros. However, there exists a DBW of the language consisting of all words with infinitely many zeros:

Let \(L_1, L_2\) be any two languages. Suppose \(L_1 = L(A_1), L_2 = L(A_2)\), where \(A_1 = (\Sigma, Q_1, q_{01}, \delta_{1}, T_1)\) and \(A_2 = (\Sigma, Q_2, q_{02}, \delta_{2}, T_2)\).

Consider the automaton that simulates the transitions of \(A_1, A_2\) at the same time: \(A = (\Sigma, Q_1 \times Q_2, (q_{01}, q_{02}), \delta, (T_1 \times Q_2) \cup (Q_1 \times T_2))\), where \(\delta (q, q', a) = (\delta_{1} (q, a), \delta_{2}(q', a))\). Each state of \(A\) is a pair of states of \(A_1, A_2\).

Then \(A\) accepts a word iff the run with the word visits \((T_1 \times Q_2) \cup (Q_1 \times T_2)\) infinitely many times, which is equivalent to visiting \(T_1\) infinitely often, or visiting \(T_2\) infinitely often, or visiting both infinitely often. This means that the word is in \(L_1 \cup L_2\). Thus, \(L(A) = L_1 \cup L_2\).

Let \(A_1, A_2\) be two automata and \(L_1 = L(A_1), L_2 = L(A_2)\). The tuples of \(A_1, A_2\) use the same notation as above.

\(L_1 \cap L_2\) consists of the words that visit both target sets infinitely many times, which is equivalent to alternating between both target sets infinitely many times (before switching to the other target set, can visit the same target set multiple times).

Consider two copies of the “joint” automata \(A_1 \times A_2\) \(A = (\Sigma, Q_1 \times Q_2 \times \{ L, R \}, (q_{01}, q_{02}) \times \{ L\}, \delta, T)\). We want to modify the transitions such that once the run reaches a target state in one copy, it switches to the other copt and continue the transition, so that it cannot visits target states in the same copy consecutively. We define the target set to be \(T = Q_1 \times T_2 \times \{ R \}\) and \(\delta\) by:

A run in \(A\) visits \(Q_1 \times T_2 \times \{ R \}\) infinitely often iff it visits \(Q_1 \times T_2 \times \{ L \}\) infinitely often: Once it visits \(Q_1 \times T_2 \times \{ R \}\), it switches to \(Q_1 \times Q_2 \times \{ L \}\), and visits \(Q_1 \times T_2 \times \{ L \}\) zero or more times until it visits \(T_1 \times Q_2 \times \{ L \}\). vice versa.

Let \(A_1 = (\Sigma, Q_1, Q_{01}, \delta_{1}, T_1)\) and \(A_2 = (\Sigma, Q_2, Q_{02}, \delta_{2}, T_2)\) and \(L_1, L_2\) be their languages, resp. We define \(A = (\Sigma, Q_1 \times \{ 1 \} \cup Q_2 \times \{ 2 \}, Q_{01} \times \{ 1 \} \cup Q_{02} \times \{ 2 \}, \delta_{1} \cup \delta_{2}, T_1 \times \{ 1 \} \cup T_2 \times \{ 2 \})\), where \((\delta_{1} \cup \delta_{2})((q, 1), a) = \delta_{1}(q, a), (\delta_{1} \cup \delta_{2})((q, 1), a) = \delta_{2}(q, a)\).

Basically, we keep two isolated components in \(A\). Then every accepting word in \(A_{i}\) corresponds to an accepting word in \(A\) starting from \(Q_{0i} \times \{ i \}\), and vice versa.

The same proof as DBW works. The initial set becomes \(Q_1 \times Q_2 \times \{ L \}\). The definition for \(\delta\) becomes \(\delta(q_1, q_2, L, a) = \delta_{1}(q_1, a) \times \delta_{2}(q_2, a) \times \{ L \}\) if \(q_1 \notin T_1\), etc.

Let \(A = (\Sigma, Q, q_0, \delta, T)\) be a DBW. Intuitively, in a complement NBW \(B\) with the “same” (not exactly) set of states as \(A\), the accepting words should never see \(T\) after finitely many steps.

We define \(B = (\Sigma, Q', Q_0, \delta', T')\) as follows: \(Q' = (Q \times \{ 1 \}) \cup ((Q \setminus T) \times \{ 2 \})\), i.e., \(Q\) plus an extra copy of \(Q \setminus T\). \(Q_0 = \{ (q_0, 1) \}\). \(T' = (Q \setminus T) \times \{ 2 \}\). \(\delta'(q, 1, a) = \{\delta(q, a)\} \times \{ 1, 2 \}\), \(\delta'(q, 2, a) = (\{ \delta(q, a) \} \times \{ 2 \}) \cap T'\).

The accepting words of \(B\) are not accepted by \(A\): They visit \(T'\) infinitely many times, and will never visit \(T \times \{ 1 \}\) (corresponds to \(T\) in \(A\)) once entering \(T'\).

Conversely, the accepting words of \(A\) are not accepted by \(B\): To visit \(T\) (\(T \times \{ 1 \}\) in \(B\)) infinitely often, they cannot ever enter \(T'\).

A run corresponds to an outcome, and an accepting run, which visits \(T\) infinitely often, corresponds to a winning outcome starting from an initial vertex in the game.

Since the outcome is solely controlled by player 1, the condition is equivalent to \(Q_0 \cap Win_{1}(Buchi(T)) \neq \emptyset\).

We provide a reduction from 3-coloring, which is a classic NP-complete problem.

Given a (undirected) graph \(G = (V, E)\), let \(\Sigma = V \times \{ r, g, b \}\). We create the following NBWs:

1. The first NBW \(A\) is defined to accept all words that, when ignoring the colors, are not valid paths in \(G\). That is, a word \((v_1, c_1), (v_2, c_2), (v_3, c_3), \dots \) is accepting iff \(\rho = \langle v_1, v_2, v_3, \dots \rangle\) is an invalid path in \(G\).

   \(A = (\Sigma, V \cup \{ \bot, q_0 \}, \{ q_0 \}, \delta, \{ \bot \})\) with Buchi condition, where:

   \begin{align*} \delta(q_0, (v, c)) = v, \delta(u, (v, c)) = \begin{cases} v, & \text{if } (u, v) \in E\\ \bot, & \text{if } (u, v) \notin E \end{cases}, \delta(\bot, (v, c)) = \bot. \end{align*}

   A word is accepted by \(A\) iff the run ever transits through \((u, (v, c))\) for some \((u, v) \notin E\). Thus, the path associated with every accepting word contains an edge that is not in \(E\), and hence is invalid.

2. The second NBW \(B\) is defined to accept all words in which there is a vertex that appears with two different colors.

   \(B = (\Sigma, A \cup \{ q_0 \}, \{ q_0 \}, \delta, B\) with Buchi condition, where \(A = \{ a_{v, c_1, c_2} | v \in V, c_1, c_2 \in \{ r, g, b \}, c_1 \neq c_2 \}\), \(B = \{ b_{v, c_1, c_2} | v \in V, c_1, c_2 \in \{ r, g, b \}, c_1 \neq c_2 \}\), and

   \begin{align*} q_0 \in \delta(q_0, *), \forall c_1, c_2 \in \{ r, g, b \}, c_1 \neq c_2: &a_{v, c_1, c_2} \in \delta(q_0, (v, c_1)), \\ & a_{v, c_1, c_2} \in \delta(a_{v, c_1, c_2}, *),\\ & b_{v, c_1, c_2} \in \delta(a_{v, c_1, c_2}, (v, c_2)), \\ & b_{v, c_1, c_2} \in \delta(b_{v, c_1, c_2}, *). \end{align*}

   An accepting word is of the form \(\dots (v, c_1) \dots (v, c_2) \dots \).

   

3. The third NBW \(C\) is defined to accept all words that do not contain all edges of the graph. It is rather complicated to define \(C\) in expression, so we only show a subpart of it: The initial vertex \(Q_0\) includes \(q_{u,v}\) for all undirected edges \((u, v) \in E\). The subpart for an edge \((u, v) \in E\) is:

   which accpets all the words that at least miss the edge \((u, v)\) (in either direction).

4. The fourth NBW \(D\) is defined to accepts all the words that have the same color twice in a row.

   

5. The NBW \(E = A \cup B \cup C \cup D\) (\(L(E) = L(A) \cup L(B) \cup L(C) \cup L(D)\)).

We claim that \(E\) is universal iff \(G\) is not 3-colorable, i.e., \(E\) is not universal iff \(G\) is 3-colorable.

Only if side: \(E\) does not accept a word iff the word (a) is a valid path in \(G\), (b) assigns a unique color to each vertex, (c) visits all edges of \(G\), and (d) does not have the same color in a row. This is equivalent to that the word represent a valid 3-coloring of the graph.

If side: If \(G\) has a valid 3-coloring, then any infinite path that visits all edges together is an infinite word that is not accepted by \(E\).

Vertex 1 must have three edges of the same color, say blue. Consider the three vertices connected with 1 by blue edges. There are two cases: (1) At least two of them are connected by a blue edge, in which a blue triangle is formed. (2) All of them are connected by red edges, in which a red triangle is formed.

Let \(a_1 \in V\) be an arbitrary vertex. Since there are finitely many colors, there is a color \(c_1\) such that \(a_1\) has infinitely many neighbours with edge of color \(c_1\). Let the set of these neighbours be \(V_1\).

Consider the infinite graph \(G[V_1] = (V_1, V_1 \times V_1)\). For the same reason, there exists a vertex \(a_2\) and a color \(c_2\) with the same properties. Continuing this process forever, we get three infinite sequences \(a_1, a_2, \dots \), \(c_1, c_2, \dots \), \(V_1, V_2, \dots \).

Thus, there is a color \(c'\) that appears infinitely many times in \(c_1, c_2, \dots \). Let \(V' = \{ a_{i} | c_{i} = c' \}\). Clearly, \(V'\) (\(G[V']\)) is an infinite monochrome clique.

Let \(w = w_1 w_2 \dots \) be any infinite word, where each \(w_{i}\) is a symbol. We define \(w[i .. j) = w_{i} w_{i+1} \dots w_{j-1}\). Consider the infinite complete graph \(G(\mathbb{N} , \mathbb{N} \times \mathbb{N} )\). We view equivalence classes as colors, and color the edge \(\{ i,j \}\) with the (unique) \(L_{f}\) that contains \(w[i .. j)\).

By the Ramsey theorem, there is a color \(L_{g}\) such that there is an infinite monochrome clique \(i_0 < i_1 < \dots \) in which edges are all colored \(L_{g}\). Particularly, \(\{ i_0, i_1 \}, \{ i_1, i_2 \}, \dots \) all have color \(L_{g}\). Thus, \(w\) can be decomposed as \(w[1.. i_0) w[i_0 .. i_1) w[i_1 .. i_2) \dots \), implying that \(w \in L_{f} (L_{g})^{\omega}\), where \(L_{f}\) is the class containing \(w[1.. i_0)\).

Let \(w \in L_{f} (L_{g}) ^{\omega}\), \(w = w_1 w_2 w_3 \dots \) where \(w_1 \in L_{f}\) and \(w_2, w_3, \dots \in L_{g}\) are finite words. Suppose \(w \in L(A)\), then by the definition of equivalence class, we can replace \(w_{i}\) by any word in the same class without affecting the times the run visits \(T\). Thus, the altered infinite words should also be \(\in L(A)\).

There are finitely many \(L_{f}\), so there are finitely many sets \(L_{f} (L_{g}) ^{\omega}\).

We have an NBW for every \(L_{g} ^{\omega}\): Take the NFA for \(L_{g}\). For each accepting state, create edges that the initial states have. The initial states and accepting states for the NBW are the same as the NFA.

We have an NBW for every \(L_{f} (L_{g}) ^{\omega}\): Take the NBW for \(L_{g} ^{\omega}\) and the NFA for \(L_{f}\). For each accepting state of the NFA, create edges that the initial states of the NBW have. The initial states of the resulting NBW are the intial states of the NFA, and the accepting states of the resulting NBW are the accepting states of the NBW for \(L_{g} ^{\omega}\).

Then take the union of NBWs of all \(L_{f} (L_{g}) ^{\omega}\) that does not intersect with \(L(A))\). Since every infinite word is in some \(L_{f} (L_{g}) ^{\omega}\), all the words in \(L(A) ^{c}\) are included.