Minimiser les automates acceptant les mots (c'est-à-dire des mots infinis)

Quelle est l'approche standard pour minimiser Büchi-Automata (ou aussi Müller-Automata)? Le transfert de la technique habituelle à partir de mots finis, c'est-à-dire la mise à égalité de deux états si les mots "en cours d'exécution" des états acceptés sont les mêmes, ne fonctionnera pas. Par exemple, considérons le Büchi-Automoton acceptant tous les mots avec un nombre infini de a composé de deux états, un état initial et un état final, et l'état final est entré chaque fois qu'un a est lu, et l'état initial est entré chaque fois qu'un un symbole différent est lu. Les deux états sont considérés comme égaux par la définition ci-dessus, mais leur effondrement produit un automate composé d'un seul état, et acceptant ainsi tous les mots.

En général, $\omega$ langues ne peuvent pas avoir réguliers réguliers une DBW minimale unique. Par exemple, le langage "infiniment de a et infiniment de b" a deux DBW à 3 états (dans l'image, remplacez $\neg a$ par $b$ ):

Comme vous pouvez le voir, ils ne sont pas topologiquement équivalents.

Par conséquent, le problème de minimisation est plus difficile que le cas fini, et en fait, il est NP-complet .

Cette question a généré beaucoup de littérature dans les années 80, en partie à cause d'une mauvaise approche du problème. C'est une histoire assez longue que je vais essayer de résumer dans cette réponse.

1. Le cas des mots finis

On peut trouver deux définitions d'un DFA minimal dans la littérature. La première consiste à définir le DFA minimal d'une langue régulière comme le DFA complet avec le nombre minimum d'états acceptant la langue. Le second est plus long à définir mais est mathématiquement plus attrayant que le premier et il donne des propriétés plus fortes.

Rappelons qu'un DFA est accessible si pour tout q ∈ Q , il y a un mot u ∈ A ∗ tel que i ⋅ u = q . Il est complet si q ⋅ un est défini pour tout q ∈ Q et un ∈ A .$(Q, A, \cdot, i, F)$$q \in Q$$u \in A^*$$i \cdot u = q$$q \cdot a$$q \in Q$$a \in A$

Soit et A 2 = ( Q 2 , A , ⋅ , i 2 , F 2 ) soient deux DFA complets et accessibles. Un morphisme de A 1 à A 2 est une fonction φ : Q 1 → Q 2 telle que${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$${\cal A}_2 = (Q_2, A, \cdot, i_2, F_2)$$\mathcal{A}_1$$\mathcal{A}_2$$\varphi:Q_1 \to Q_2$

1. ,$\varphi(i_1) = i_2$
2. ,$\varphi^{-1}(F_2) = F_1$
3. pour tout et a ∈ A , φ ( q ) ⋅ a = φ ( q ⋅ a ) .$q \in Q_1$$a \in A$$\varphi(q)\cdot a=\varphi(q\cdot a)$

On peut montrer que ces conditions impliquent que est nécessairement surjectif (et donc | Q 2 | ⩽ | Q 1 | ). De plus, il y a au plus un morphisme de A 1 à A 2 et si ce morphisme existe, alors A 1 et A 2 reconnaissent le même langage. Maintenant, on peut montrer que pour chaque langue L , il y a un DFA complet unique , accessible A L accepter L et tel que, pour tous les DFA , stockable A accepter $\varphi$$|Q_2| \leqslant |Q_1|$${\cal A}_1$${\cal A}_2$${\cal A}_1$${\cal A}_2$$L$${\cal A}_L$$L$$\cal A$$L$, Il existe un morphisme de sur A L . Cet automate est appelé DFA minimal de L . Notez encore que puisque le nombre d'états dans A L est plus petit que le nombre d'états dans A , A L est également minime dans le premier sens.$\cal A$${\cal A}_L$$L$${\cal A}_L$$\cal A$${\cal A}_L$

Il convient de mentionner qu'il existe également une définition algébrique appropriée pour les DFA incomplets . Voir [Eilenberg, Automata, Languages ​​and Machines , vol. A, Academic Press, 1974] pour plus de détails.

2. Retour aux mots infinis

L'extension de la première définition ne fonctionne pas, comme l'a montré Shaull dans sa réponse. Et malheureusement, on peut aussi montrer que la propriété universelle de la deuxième définition ne s'étend pas aux mots infinis, sauf dans quelques cas particuliers.

Est-ce la fin de l'histoire? Attendez une seconde, il y a un autre objet minimal qui accepte les langages normaux ...

3. L'approche syntaxique

Revenons d'abord aux mots finis. Rappelons que la langue de A * est reconnu par un monoid M s'il y a une surjective monoid morphisme f : A * → M et d' un sous - ensemble P de M de telle sorte que f - 1 ( P ) = L . Encore une fois, il existe un monoïde M ( L ) , appelé le monoïde syntaxique de L , qui reconnaît L et est un quotient de tous les monoïdes reconnaissant $L$$A^*$ $M$$f:A^* \to M$$P$$M$$f^{-1}(P) = L$$M(L)$$L$$L$$L$. Ce monoïde syntaxique peut être défini directement comme le quotient de par la congruence syntaxique ∼ L de L , définie comme suit: u ∼ L v  si et seulement si, pour tout  x , y ∈ A ∗ ,  x u y ∈ $A^*$ $\sim_L$$L$ La bonne nouvelle est que cette fois, cette approche a été étendue à des mots infinis, mais il a fallu beaucoup de temps pour découvrir les notions appropriées. En premier, le (A congruence syntaxique pour rationnels notion appropriée d'une congruence syntaxique a été trouvé par A. Arnoldco-langues,Sci. Theoret. Comput.39, 2-3 (1985), 333-335). L'extension des monoïdes syntaxiques à la définition de mots infinis nécessitait un type d'algèbres plus sophistiqué, appelé de nos joursalgèbres de Wilkeen l'honneur de T. Wilke, qui fut le premier à les définir (T. Wilke, Une théorie algébrique pour les langages réguliers de fini et d'infini mots,Int. J. Alg. Comput.3

4. Conclusion

Il existe donc une notion mathématiquement saine d'un objet minimal acceptant un -langue régulier donné , mais il ne repose pas sur des automates. C'est en fait un fait assez générique: les automates sont un outil algorithmique très puissant, mais ils ne sont pas toujours suffisants pour traiter des questions mathématiques sur les langues.$\omega$