Algorithme de Brzozowski pour la minimisation DFA

L'algorithme de minimisation DFA de Brzozowski crée un DFA minimal pour DFA en:$G$

1. inverser tous les bords de , faisant de l'état initial un état accepté, et des états acceptés initiaux, pour obtenir un NFA pour le langage inverse,$G$$N'$
2. en utilisant la construction du jeu de puissance pour obtenir pour le langage inverse,$G'$
3. inverser les bords (et swap initial-accepter) dans pour obtenir un NFA pour la langue d'origine, et$G'$$N$
4. faire la construction du jeu de puissance pour obtenir .$G_{\min}$

Bien sûr, puisque certains DFA ont un grand DFA inverse exponentiel, cet algorithme s'exécute en temps exponentiel dans le pire des cas en termes de taille de l'entrée, permet donc de garder une trace de la taille du DFA inverse.

Si $N$ est la taille du DFA d'entrée, $n$ est la taille du DFA minimal et $m$ la taille du DFA inverse minimal, alors quel est le temps d'exécution de l'algorithme de Brzozowski en termes de $N$ , $n$ et $m$ ?

En particulier, dans quelle relation entre $n$ et $m$ l'algorithme de Brzozowski surpasse-t-il les algorithmes de Hopcroft ou de Moore?

J'ai entendu dire que sur des exemples typiques de pratique / application , l'algorithme de Brzozowski surpasse les autres. De manière informelle, à quoi ressemblent ces exemples typiques?

Voici une réponse partielle concernant votre troisième question. En fait, l'algorithme de Brzozowski ne surpasse vraiment pas tous les autres algorithmes si clairement dans la minimisation DFA.

Dans [1], les auteurs étudient les performances pratiques des algorithmes de minimisation DFA / NFA. Les algorithmes sont ceux de Hopcroft, Brzozowski et deux variantes de Watson. Ils concluent qu'il n'y a pas de gagnant clair, mais l'algorithme de Hopcroft fonctionne mieux pour les DFA avec de petits alphabets. Pour les NFA, Brzozowski est clairement le plus rapide.

Le document lui-même est assez court et clairement écrit. Il y a aussi des discussions et des références supplémentaires qui pourraient être utiles.

[1] Almeida M., Moreira N. et Reis R. Sur les performances des algorithmes de minimisation des automates, quatrième conférence sur la calculabilité en Europe, juin 2008.

La plupart des éléments ci-dessous sont tirés de Parsing Theory de Sippu et Soisalon-Soininen.

Soit l'ensemble des états du DFA. Soit T l'alphabet d'entrée. Soit | M | = O ( | T | ⋅ | Q | ) soit la taille de la machine. L'exercice 3.40 donne un algorithme O ( | T | ⋅ | Q | 2 ) pour la minimisation de l'état. Comme Wikipedia le décrit , l'algorithme de Hopcroft a un temps d'exécution de O ( | T | ⋅ | Q | ⋅ $Q$$T$$|M|=O(|T| \cdot |Q|)$$O(|T|\cdot|Q|^2)$ et l'algorithme de Moore a un temps d'exécution de O ( | T | 2 ⋅ | Q | ) .$O(|T| \cdot |Q| \cdot \log|T|)$$O(|T|^2 \cdot |Q|)$

Le théorème 3.30 indique que la construction du sous-ensemble peut être effectuée dans ce qui donne un automate de taille O ( 2 | T | + log | Q | ) (en fait, si le l'automate résultant a | T ′ | états, le temps d'exécution est ( | T ′ | + | T | ⋅ |$O(2^{|T|+\log|T|+\log|Q|})$$O(2^{|T|+\log|Q|})$$|T'|$). Les deux inversions et la deuxième déterminisation sont donc sans conséquence dans le temps d'exécution, de sorte que le temps d'exécution asymptotique de l'algorithme de Brzozowski est le même que celui de la construction du sous-ensemble.$(|T'| + |T|\cdot|M|) \cdot |Q|$

Cela signifie que dans le pire des cas, l'algorithme de Brzozowski est exponentiellement plus lent que les trois autres algorithmes. Notez que le pire des cas se produit vraiment: l'exemple classique du NFA pour la langue a k + 1 états et son DFA minimal correspondant a O ( 2 k ) états, tandis que l'inverse du NFA est déterministe, l'exécution de l'algorithme de Brzozowski sur ce NFA inversé déclenche le comportement le plus défavorable.$(a|b)^*a^k$$k+1$$O(2^k)$

Cependant, si la construction du sous-ensemble donne un automate de taille , son temps de fonctionnement est également O ( | T | 2 ⋅ | Q | 2 ) , ce qui est souvent le cas sur les entrées réelles. En outre, si l'on prend soin lors du calcul de la fermeture d'un état, cela peut être fait beaucoup plus rapidement dans la plupart des cas (c'est-à-dire dans les cas où la fermeture est petite), en économisant un facteur | T $|T'|=O(|T|)$$O(|T|^2 \cdot |Q|^2)$$|T|$dans la pratique (essentiellement pour la même raison que les fermetures transitives peuvent être calculées assez rapidement sur des exemples réels). De plus, si les automates d'entrée et intermédiaires sont rares, ce qui signifie que les états ont peu de transitions, alors un facteur est enregistré, ce qui donne un temps de fonctionnement O ( | T | ⋅ | Q | ) sur les «bonnes» entrées.$|Q|$$O(|T| \cdot |Q|)$

Malheureusement, je ne connais pas suffisamment les algorithmes de Hopcroft ou de Moore pour donner une analyse de leurs temps de fonctionnement dans des cas typiques. Wikipedia parle d'un temps d'exécution dans certains cas, ce qui rendrait les trois algorithmes comparables.$O(|T| \log \log |T|)$

De Felice et Nicaud montrent que les algorithmes de Brzozowski sont asymptotiquement hyper-polynomiaux. David a montré que, pour plusieurs distributions sur les états finaux, l'algorithme de Hopcroft est plus lent que l'algorithme de Moore.

Les références

S. De Felice et C. Nicaud, "Brzozowski Algorithm is Generically Super-Polynomial for Deterministic Automata". In Proceedings of 17th International Conference on Developments in Language Theory (DLT 2013) , Lecture Notes in Computer Science, pp. 170-190, 2013. ( PDF )

J. David, "Complexité moyenne des algorithmes de Moore et Hopcroft". Informatique théorique , 417: 50–65, 2012. ( Science Direct )