# Minimizing Automata accepting $\omega$-words (i.e. infinite words)

What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" of the states which are accepted are the same, will not work. For example consider the Büchi-Automoton accepting all words with an infinite number of a's consisting of two states, a initial and a final state, and the final state is entered each time an a is read, and the initial state is entered each time a different symbol is read. Both states are considered equal by the above defintion, but collapsing them yields an automata consisting of a single state, and thereby accepting every words.

In general, $\omega$-regular languages may not have a unique minimal DBW. For example, the language "infinitely many a's and infinitely many b's" has two 3-state DBWs (in the picture replace $\neg a$ by $b$):

As you can see, they are not topologically equivalent.

Hence, the minimization problem is harder than the finite case, and in fact, it is NP-complete.

• I found three 3-state deterministic Büchi-Automata, two are structurally very similar (they just differ by the labels on their transitions), but would you mind nonetheless to give your machines, just for comparison :) Thanks for the article! Dec 26, 2014 at 23:23
• @Stefan - added the example. Dec 27, 2014 at 7:36
• The left one I have too, but I also have a different one, I posted it as an edit in my question. Dec 27, 2014 at 11:31
• The automaton you added is incorrect - it doesn't accept the word $(bab)^\omega=babbabbabbab...$ Dec 27, 2014 at 11:36
• Considering DBWs, I was wondering if the problem is still hard if we consider a $constant$ alphabet, let say binary. What do you think? And regarding equivalent states, can't we somehow bound the number of equivalent states we need?! For example, i believe one can bound the number of states with only one outgoing arrow(labeled "true"). Dec 5, 2017 at 10:19

This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer.

1. The case of finite words

One can find two definitions of a minimal DFA in the literature. The first one is to define the minimal DFA of a regular language as the complete DFA with the minimum number of states accepting the language. The second one is longer to define but is mathematically more appealing than the first one and it gives stronger properties.

Let us recall that a DFA $(Q, A, \cdot, i, F)$ is accessible if for all $q \in Q$, there is a word $u \in A^*$ such that $i \cdot u = q$. It is complete if $q \cdot a$ is defined for all $q \in Q$ and $a \in A$.

Let ${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$ and ${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$ be two complete, accessible DFAs. A morphism from $\mathcal{A}_1$ to $\mathcal{A}_2$ is a function $\varphi:Q_1 \to Q_2$ such that

1. $\varphi(i_1) = i_2$,
2. $\varphi^{-1}(F_2) = F_1$,
3. for all $q \in Q_1$ and $a \in A$, $\varphi(q)\cdot a=\varphi(q\cdot a)$.

One can show that these conditions imply that $\varphi$ is necessarily surjective (and thus $|Q_2| \leqslant |Q_1|$). Furthermore, there is at most one morphism from ${\cal A}_1$ to ${\cal A}_2$ and if this morphism exists, then ${\cal A}_1$ and ${\cal A}_2$ recognize the same language. Now, one can show that for every language $L$, there is a unique complete accessible DFA ${\cal A}_L$ accepting $L$ and such that, for every complete accessible DFA $\cal A$ accepting $L$, there is a morphism from $\cal A$ onto ${\cal A}_L$. This automaton is called the minimal DFA of $L$. Note again that since the number of states in ${\cal A}_L$ is smaller than the number of states in $\cal A$, ${\cal A}_L$ is also minimal in the first sense.

It is worth mentioning that there is also a suitable algebraic definition for incomplete DFAs. See [Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974] for more details.

2. Back to infinite words

Extending the first definition does not work, as shown by Shaull in his answer. And unfortunately one can also show that the universal property of the second definition does not extend to infinite words, except in a few particular cases.

Is it the end of the story? Wait a second, there is another minimal object that accepts regular languages...

3. The syntactic approach

Let us first return again to finite words. Recall that a language $L$ of $A^*$ is recognized by a monoid $M$ if there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Again, there exists a monoid $M(L)$, called the syntactic monoid of $L$, which recognizes $L$ and is a quotient of all monoids recognizing $L$. This syntactic monoid can be defined directly as the quotient of $A^*$ by the syntactic congruence $\sim_L$ of $L$, defined as follows: $$\text{u \sim_L v if and only if, for all x, y \in A^*, xuy \in L \iff xvy \in L}$$ The good news is that this time, this approach has been extended to infinite words, but it took a long time to discover the appropriate notions. First, the suitable notion of a syntactic congruence was found by A. Arnold (A syntactic congruence for rational $\omega$-languages, Theoret. Comput. Sci. 39,2-3 (1985), 333–335). Extending syntactic monoids to the setting of infinite words required a more sophisticated type of algebras, called nowadays Wilke algebras in honor of T. Wilke, who was the first to define them (T. Wilke, An algebraic theory for regular languages of finite and infinite words, Int. J. Alg. Comput. 3 (1993), 447–489). More details can be found in my book Infinite words coauthored with D. Perrin.

4. Conclusion

Thus there is a mathematically sound notion of a minimal object accepting a given regular $\omega$-language, but it does not rely on automata. This is actually a rather generic fact: automata are a very powerful algorithmic tool, but they are not always sufficient to treat mathematical questions on languages.

Minimization of automata on infinite words is still a very mysterious problem. Although most of the results are negative, as pointed by Shaull, for example, minimization of DBWs (deterministic Büchi word automata) is NP-complete, it is worth mentioning that the above hardness result works only for automata with state-based acceptance: the acceptance condition of the automaton is a subset $$\alpha$$ of states, and a run is accepting if it visits states in $$\alpha$$ infinitely often. The problem with the hardness result is that it relies heavily on the fact that we consider state-based acceptance. When, however, we consider automata with transition-based acceptance, the minimization problem becomes open, and in fact, a PTIME algorithm here would imply a polynomial 2-approximation for the former problem.

The closest that was gotten to is minimization of transition-based good-for-games coBüchi word automata -- a special case of nondeterministic automata that we can resolve their nondeterministic choices based only on the past. Formally, there exists a function $$f$$ that maps finite words to states, and following $$f$$ upon reading a word in the language of the automaton, induces an accepting run.

So back to your question, it is well-known now that minimization of transition-based good-for-games coBüchi word automata can be solved in PTIME, and in fact some parts of the minimization algorithm follow that idea of merging or collapsing two states that behave similarly into one state: states that are equivalent and also have the same language in the structure that we get after removing transitions in $$\alpha$$. Note also that the latter implies a 2-approximation algorithm for minimization of state-based good-for-games coBüchi word automata, which is known to be NP-complete: the same reduction for minimization of DBWs applies also to this class.

There is more to tell about the minimization problem, to be fair, but I just wanted to highlight that the problem being hard did not end the quest, it just started it, and techniques that are based on merging states can be useful, but it is difficult and needs to be done carefully.