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

Question

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.

Answer 1

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.

Answer 2

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.