Minimisation d'un automate fini déterministe

Dans cet automate, tous les états sont accessibles, les états c, d et e sont indistinguables, ainsi que les états a et b.

Automate minimal équivalent. Les états indistinguables sont regroupés en un seul état.

En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates.

Les algorithmes généraux les plus connus - nommés d'après leurs inventeurs - sont l'algorithme de Brzozowski, l'algorithme de Moore, et l'algorithme de Hopcroft. D'autres algorithmes spécifiques existent, par exemple pour la minimisation d'automates reconnaissant des ensembles finis de mots, comme l'algorithme de Revuz et ses variantes. Les algorithmes ont aussi été étendus à des cas plus généraux, comme les automates avec sortie (automate de Moore, automate de Mealy) ou les transducteurs finis. Il n'existe pas de procédé analogue pour la minimisation d'automates plus généraux, comme les automates à pile ou les automates linéairement bornés.

Une application importante de la minimisation des automates finis déterministes est le test de l'équivalence de deux automates finis, c'est-à-dire le fait de décider s'ils reconnaissent le même langage. C'est une conséquence de l'unicité de l'automate fini minimal, à un renommage des états près. Pour répondre à la question, il suffit de minimiser les deux automates et de tester si leurs versions minimales sont égales.

Étant donné l'importance de la minimisation, cette opération fait partie de la plupart des logiciels de manipulation d'automates.

Automate minimal déterministe

Tout langage rationnel est reconnu par un automate fini déterministe et complet, et parmi ces automates, il en existe un ayant un nombre minimal d'états. Cet automate est unique au renommage des états près; c'est l’automate minimal du langage. L'intérêt d'un automate minimal est que le coût en espace de la représentation est minimisé.

Parmi les automates finis reconnaissant un langage donné, il peut exister des automates non déterministes qui reconnaissent ce langage, et qui ont exponentiellement moins d'états que l'automate fini déterministe minimal. L'adjectif minimal s'applique ici aux automates déterministes. De même, il peut exister des automates non déterministes non isomorphes ayant un nombre minimal d'états et reconnaissant le même langage. L'unicité de l'automate déterministe minimal est donc une propriété remarquable, valable uniquement dans ce cas.

Les automates considérés dans ce cadre sont non seulement déterministes, mais aussi complets. Un automate est complet si sa fonction de transition est partout définie, en d'autres termes si, pour tout état et toute lettre, il existe une transition sortant de cet état et étiquetée par cette lettre. Un automate fini déterministe émondé peut avoir un état de moins, si l'automate fini complet correspondant a un état puits.

États accessibles

On considère un automate fini déterministe complet

${\mathcal {A}}=(Q,i,T)$

sur un alphabet $A$. Ici $Q$ est l'ensemble des états, $i$ est l'état initial, $T$ est l'ensemble des états terminaux. La fonction de transition est notée par un simple point. Un état $q$ est accessible s'il existe un mot $w$ tel que $q=i\cdot w$, il est inaccessible sinon. Les états inaccessibles peuvent être supprimés sans modifier le langage reconnu par l'automate, et l'automate minimal ne possède que des états accessibles. Un automate est accessible si tous ses états sont accessibles.

Les états accessibles d'un automate peuvent être calculés au moyen d'un parcours du graphe qui représente l'automate. Ce sont les états qui sont atteints par un chemin depuis l'état initial. Il suffit donc d'adapter l'algorithme usuel de parcours d'un graphe à ce cas. La complexité en temps de l'algorithme est linéaire en fonction du produit $\operatorname {Card} (Q)\times \operatorname {Card} (A)$ du nombre d'états par la taille de l'alphabet. Le code suivant en est une réalisation :

Calcul des états accessibles

let états_accessibles:= {i};
let états_nouveaux:= {i};
do {
    temp := l'ensemble vide;
    for each q in états_nouveaux do
        for all a in A do
            temp := temp ∪ {q.a)};
        end;
    end;
    états_nouveaux := temp \ états_accessibles;
    états_accessibles := états_accessibles ∪ états_nouveaux;
} while(états_nouveaux ≠ the empty set);
état_inaccessibles := Q \ états_accessibles;

 

États indistinguables

Soit

${\mathcal {A}}=(Q,i,T)$

un automate déterministe complet. Deux états $p$ et $q$ sont indistinguables ou inséparables si tout mot $w$ reconnu par ${\mathcal {A}}$ à partir de $p$ est aussi reconnu à partir de $q$ et réciproquement, formellement si pour tout mot $w$ :

$p\cdot w\in T\iff q\cdot w\in T$.

Deux états sont séparables s'ils ne sont pas inséparables. Un critère de minimalité utile est le suivant :

Critère de minimalité —  Un automate fini déterministe complet et accessible est minimal si et seulement ses états sont deux-à-deux séparables.

Une façon plus condensée de présenter ce critère est d'introduire les langages à droite (« right languages » en anglais) : le langage à droite d'un état $q$ est par définition le langage

$L_{q}({\mathcal {A}})=\{w\in A^{*}\mid q\cdot w\in T\}$.

C'est donc l'ensemble des mots reconnus par l’automate en prenant $q$ comme état initial. Alors deux états sont inséparables si et seulement s'ils ont même langage à droite.

L'équivalence de Nerode est la relation, notée $\sim$, sur l'ensemble des états définie par

$q\sim q'\iff L_{q}({\mathcal {A}})=L_{q'}({\mathcal {A}})$ .

Deux états équivalents pour l'équivalence de Nerode sont donc indistinguables et réciproquement. Un automate est donc minimal, d'après l'énoncé ci-dessus, exactement quand son équivalence de Nerode est l’égalité.

Ne pas confondre cette équivalence, définie sur les états, avec la relation de Myhill-Nerode, du théorème de Myhill-Nerode, qui est définie sur les mots : deux mots sont équivalents pour la relation de Myhill-Nerode s'ils définissent le même résiduel ou quotient à droite. Les états de l’automate minimal sont en bijection avec les classes de l'équivalence de Myhill-Nerode.

Un algorithme élémentaire

Un algorithme élémentaire de minimisation d'un automate fini déterministe consiste à chercher des paires d'états inséparables ou indistinguables. Cette méthode se trouve dans le manuel de Hopcroft, Motwani et Ullman et celui de Peter Linz.

Algorithme de recherche d'états séparables

La méthode est un algorithme de marquage. Elle consiste à chercher et marquer des paires d'états séparables. Elle procède les paires $(p,q)$ d'états distincts comme suit :

1. Pour toute paire $(p,q)$ d'états, si $p$ est final et $q$ ne l'est pas ou vice-versa, marquer $(p,q)$ comme séparables.
2. Répéter l'opération suivante tant qu'une nouvelle paire a été marquée :

Pour toute paire $(p,q)$ et toute lettre $a$, calculer $p_{a}=p\cdot a$ et $q_{a}=q\cdot a$. Si la paire $(p_{a},q_{a})$ est marquée comme étant séparable, marquer $(p,q)$ comme séparable.

Méthode de remplissage de table

Hopcroft et. al. appellent « table-filling algorithm » (« algorithme de remplissage de table ») la mise en œuvre de l'algorithme qui consiste à remplir une table par inspection progressive des cases. Dans la table ci-dessous, une croix en case (X,Y) signifie que les états X et Y sont séparables. L'exemple suivant se trouve dans leur livre :

Exemple pour le remplissage de table. Les états terminaux sont en rose.

	A	B	C	D	E	F	G	H
B	x
C	x	x
D	x	x	x
E		x	x	x
F	x	x	x		x
G	x	x		x	x	x
H	x		x	x	x	x	x

La première étape consiste à marquer d'une croix les paires (X,Y) où X est final et Y ne l'est pas et vice-versa. Ensuite, on peut marquer l'entrée (B,A) parce que leurs images par la lettre 0 est séparable. On continue autant que possible. Les cases restées non marquées désignent des états inséparables. Ici, cela signifie donc que A et E sont indistinguables, de même que B et H et D et F.

L'algorithme de remplissage est similaire aux autres algorithmes de raffinement décrits ci-dessous. Il est facile à mettre en œuvre à la main sur de petits exemples, mais sa complexité en place et en temps est considérable, sauf à organiser l'exploration de manière disciplinée, auquel cas on se rapproche de la méthode de Moore.

Algorithme de Brzozowski

Brzozowski présente, dans son article de 1963, un algorithme de minimisation qui est basé sur la déterminisation d'un automate fini non nécessairement déterministe. Cet algorithme, conceptuellement simple, produit - de façon étonnante - un automate minimal.

La notion importante de l'algorithme est celle d'automate transposé : on modifie l'automate en échangeant les états finaux et initiaux, et en changeant le sens des transitions.

L'énoncé précis est le suivant :

Théorème — Soit ${\mathcal {A}}$ un automate fini déterministe et accessible, et soit ${\mathcal {A}}^{\sim }$ l'automate fini déterministe complet accessible obtenu à partir de l'automate transposé ${\mathcal {A}}^{R}$ par déterminisation et élimination des états inaccessibles. Alors l'automate ${\mathcal {A}}^{\sim }$ est minimal et reconnaît le langage miroir du langage reconnu par ${\mathcal {A}}$.

L'algorithme de minimisation d'un automate fini ${\mathcal {A}}$ est alors le suivant :

1. Calculer ${\mathcal {A}}^{\sim }$, en transposant l'automate puis en le déterminisant par la procédure usuelle par exemple qui ne conserve que les états accessibles;
2. Répéter l'opération sur l'automate obtenu : calculer $({\mathcal {A}}^{\sim })^{\sim }$ en transposant ${\mathcal {A}}^{\sim }$ puis en le déterminisant de la même manière.

Pour la deuxième étape, l'automate est déterministe et accessible. Par la proposition de Brzozowski, l'automate obtenu est l'automate minimal équivalent à l’automate de départ. La complexité en temps et en place de l'algorithme est exponentielle dans le pire des cas en fonction de la taille de l'automate de départ, car l'automate intermédiaire ${\mathcal {A}}^{\sim }$ peut être exponentiel. Un exemple est fourni par le langage $K_{n}$ formé de mots de longueur au moins $n$ sur un alphabet à deux lettres $a$ et $b$, et dont la $n$-ième lettre toujours un $a$, en d'autres termes :

$K_{n}=\{a,b\}^{n-1}a\{a,b\}^{*}$.

Ce langage est reconnu par un automate à $n+1$ états plus un état puits, mais son transposé, une fois déterminisé, requiert $2^{n}$ états.

Il a été observé que dans la pratique l'algorithme donne des résultats meilleurs que l'on pourrait penser. Ceci pose la question de la complexité en moyenne de l’algorithme. Un article de De Felice et Nicaud apporte une réponse à cette question : l'algorithme de Brzozowski est génériquement super-polynomial. Ce terme technique signifie la complexité en moyenne, et même que la complexité générique de l'algorithme est plus grande que tout polynôme. Le terme « complexité générique » signifie que l'on est autorisé à « ignorer », dans le calcul de la moyenne, un ensemble de cas particulièrement désavantageux, sous réserve que cet ensemble de cas soit de taille négligeable en un sens que l'on peut préciser.

Algorithmes de raffinements de partitions

Principe

Les algorithmes de Moore et de Hopcroft sont des algorithmes de raffinements de partitions. On commence, dans les deux algorithmes, avec une hypothèse naïve, en supposant que l'automate minimal n'a que deux états et, en examinant la fonction de transition, on raffine la partition initiale tant que c'est nécessaire. Le raffinement consiste à trouver des états séparables au sens défini ci-dessus : deux états $p$ et $q$ sont séparables s'il existe un mot $w$ tel que l'état $p\cdot w$ est final et $q\cdot w$ n'est pas final, ou vice-versa.

Lorsque l'algorithme de raffinement s'arrête, chaque classe de la partition représente un ensemble d'états deux-à-deux inséparables, et deux classes distinctes sont séparables. L'automate minimal est obtenu en prenant comme états les classes de la partition, et comme transitions les transitions induites sur les classes par les transitions de l'automate de départ.

Algorithme de Moore

L'algorithme de Moore pour la minimisation d'automates est dû à Moore 1956. L'algorithme maintient une partition des états, constituée initialement de deux classes, formées des états terminaux et des autres. La partition est ensuite raffinée jusqu'à obtenir une partition stable. À chaque étape, on remplace la partition courante par la partition qui est l'intersection de la partition courante et des partitions induites par les préimages des classes par les lettres de l'alphabet. L'algorithme s'arrête lorsque ce remplacement ne modifie pas la partition courante. On montre que les classes de la partition finale sont constituées d'états inséparables, et forment donc les états de l'automate minimal.

L'algorithme est décrit par le pseudo-code suivant :

P := {F, Q \ F};
répéter
    P'=P
    pour chaque a de A faire
       calculer le raffinement de P induit par a;
    remplacer P par son intersection avec ces raffinements
jusqu'à P=P'

On considère les équivalences $\sim _{0},\sim _{1},\ldots$ sur l’ensemble des états définies par

$p\sim _{h}q\iff L_{q}^{(h)}({\mathcal {A}})=L_{p}^{(h)}({\mathcal {A}})$,

où

$L_{p}^{(h)}({\mathcal {A}})=\{w\in A^{*}\mid p\cdot w\in T{\text{et }}|w|\leq h\}$.

Chaque ensemble $L_{p}^{(h)}$ est donc composé des mots de longueur au plus $h$ qui mènent de l'état $p$ à un état terminal de l’automate. Deux états sont équivalents pour la relation $\sim _{h}$ si les mêmes mots de longueur au plus $h$ mènent à des états terminaux. Cela signifie que l'on peut pas les séparer par des mots de longueur au plus $h$. Les équivalences $\sim _{h}$ sont parfois appelées équivalences de Moore d'ordre $h$. Ces équivalences se calculent facilement grâce à la propriété suivante :

Lemme — Pour deux états $p$ et $q$ et $h\geq 0$, on a

$p\sim _{h+1}q\iff p\sim _{h}q{\text{ et }}p\cdot a\sim _{h}q\cdot a{\text{ pour toute lettre }}a\in A$.

Ainsi, pour calculer l'équivalence $\sim _{h+1}$, on détermine les états qui, par une lettre, arrivent dans des classes distinctes de $\sim _{h}$ : ceux-ci sont dans des classes distinctes de $\sim _{h+1}$. Plus précisément, on détermine, pour toute lettre $a\in A$, la partition dont les classes sont constituées d'états qui, par la lettre $a$, donnent des états équivalents pour $\sim _{h}$. On forme ensuite l'intersection de ces partitions avec la partition $\sim _{h}$ elle-même.

Il est facile de vérifier que si $\sim _{k}$ et $\sim _{k+1}$ sont égales pour un entier $k$, alors $\sim _{k}$ et $\sim _{k+r}$ sont égales pour tout $r$, et que les classes d'équivalences sont formées d'états inséparables.

La complexité en temps de l'algorithme est, dans le pire des cas, $O(sn^{2})$, où $s$ est la taille de l'alphabet et où $n$ est le nombre d'états de l'automate. Chacune des étapes du raffinement peut être effectuée en temps $O(sn)$ en utilisant une variante appropriée du tri par base ou « radix sort ». À chaque étape, le nombre de classes augmente strictement, et comme au départ il y a deux classes, au plus $n-2$ étapes suffisent. En fait, la complexité est même en $O(\ell sn)$, où $\ell$ est le nombre d'étapes de l'algorithme. On peut observer que le nombre d'étapes est indépendant du nombre d'états de l'automate de départ.

La complexité en moyenne est bien meilleure. Elle est en $O(n\log n)$, et même en $O(n\log \log n)$, selon le choix du modèle retenu pour la distribution aléatoire.

Algorithme de Hopcroft

L'algorithme, appelé ainsi d'après son inventeur, est dû à John Hopcroft et il a été présenté en 1971; il opère par raffinement successif d'une partition initialement grossière de l'ensemble des états de l'automate déterministe fini à minimiser.

Principe

L'algorithme débute avec la partition la plus grossière, dont les deux classes sont composées des états terminaux et des autres. La partition est progressivement raffinée en un nombre croissant de classes plus petites. Chaque tour de l'algorithme partage des ensembles d'états en deux parties plus petites.

L'opération de base est la coupure (« splitting » en anglais). Un ensemble d'états $X$ est coupé par la paire $(Z,a)$ formée d'un ensemble $Z$ et d'une lettre $a$ si les ensembles

$X'=\{q\in X\mid q\cdot a\in Z\}$ et $X''=\{q\in X\mid q\cdot a\notin Z\}$

sont tous les deux non vides. Dans le cas contraire, on dit que $X$ est stable pour $(Z,a)$.

L'algorithme maintient un ensemble ${\mathcal {W}}$ de couples $(Z,a)$, candidats à couper des éléments de la partition en cours; cet ensemble de candidats en attente est appelé le « waiting set » en anglais.

L'algorithme est décrit par le pseudo-code suivant :

P := {F, Q \ F};                                             "Partition initiale"
W := l'ensemble vide;                                        "Candidats en attente"
for each a in A do
     ajouter (min(F, Q\F),a) à W;                            "Initialisation de l'ensemble W"
while (W ≠ l'ensemble vide) do
     choisir ensemble (Z,a) dans W et l'enlever de W
     for each X de P coupé par (Z,a) en X' et X'' do         "Calcul de la coupe"
          remplacer X in P par les deux ensembles X' et X''  "Raffinement de la partition"
          for each b in A do                                 "Mise-à-jour de l'ensemble" 
               if (X,b) est in W                             "des candidats en attente"
                    remplacer (X,b) in W par (X',b) et (X'',b)
               else
                    ajouter le plus petit de (X',b) et (X'',b) à W;
          end;
     end;
end;

Le but de l'algorithme est d'obtenir par coupes successives un automate déterministe minimal. L'algorithme procède en testant la stabilité de chaque groupe d'états de la partition $P$ par toutes les coupes possibles.

L'algorithme débute avec la partition $P$ composée de l'ensemble des états terminaux $T$ et de l'ensemble des états non terminaux $Q\setminus T$. ${\mathcal {W}}$ est l'ensemble des candidats en attente pour raffiner la partition $P$. On ajoute à ${\mathcal {W}}$ tout couple de la forme $(S,a)$, avec $a$ une lettre et $S$ le plus petit des ensembles $T$ et $Q\setminus T$.

L'algorithme choisit itérativement un ensemble $(Z,a)$ dans l'ensemble des candidats en attente ${\mathcal {W}}$, le retire de l'ensemble et, pour chaque partie $X$ de la partition courante, il teste si $X$ est coupé par $(Z,a)$. Dans l’affirmative, la partition est mise à jour en remplaçant $X$ par les deux parties $X'$ et $X''$ résultant de la coupure. De plus, l'ensemble des candidats en attente est augmenté, pour toute lettre $b$, de $(X',b)$ et $(X'',b)$ ou du plus petit de $(X',b)$ et $(X'',b)$, selon que $(X,b)$ est dans ce waiting set ou non.

A chaque itération, soit l'ensemble ${\mathcal {W}}$ perd un élément, soit la partition est raffinée. Comme la partition ne peut être raffinée indéfiniment parce que l'automate est fini, le nombre d'itérations est donc fini. Ceci prouve donc la terminaison de l'algorithme.

Complexité et optimalité

La complexité en temps de l’algorithme de Hopcroft, dans le pire des cas, est $O(s\cdot n\log n)$ où $n$ est le nombre d'états de l'automate et $s$ est la taille de l'alphabet. La borne est conséquence du fait que, pour chacune des $sn$ transitions de l'automate, les ensembles retirés du waiting set qui contiennent l'état d'arrivé d'une transition ont une taille diminuée de moitié au moins à chaque fois, donc chaque transition participe à au plus $O(\log n)$ étapes de coupure dans l'algorithme.

L'algorithme de Hopcroft est le plus efficace des algorithmes de minimisation connus en 2010. L'algorithme initial demande que l'automate de départ soit déterministe et complet. On peut adapter l'algorithme au cas des automates déterministes finis incomplets. L'implémentation est en temps $O(n+m\cdot \log m)$, où $m$ est le nombre de transitions de l'automate. On a toujours $m\leq sn$.

Il reste un certain degré de liberté dans le choix du candidat que l'on retire de l'ensemble ${\mathcal {W}}$ des candidats en attente. Cela dépend aussi du choix de la structure de donnée choisie : l'ensemble peut être par exemple organisé en pile (structure LIFO) ou en file (structure FIFO). Il a été prouvé qu'un choix approprié de la stratégie permet à l'algorithme de Hopcroft d'être toujours meilleur que l'algorithme de Moore. En particulier, l'algorithme a une complexité en moyenne en $O(sn\log \log n)$.

Minimisation d'automates non déterministes

Les algorithmes décrits ci-dessus ne s'appliquent pas à des automates non déterministes. Alors que la notion d'automate minimal, compris comme automate ayant un nombre minimal d'états, a parfaitement un sens dans le cas des automates non déterministes, l'unicité n'est plus assurée, et le problème général est PSPACE-complet au sens de la théorie de la complexité.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « DFA minimization » (voir la liste des auteurs).

Bibliographie

Articles historiques

• Janusz Brzozowski, « Canonical regular expressions and minimal state graphs for definite events », dans Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 1963 (MR 0175719), p. 529–561.
• Edward F. Moore, « Gedanken-experiments on sequential machines », dans Automata studies, Princeton, N. J., Princeton University Press, coll. « Annals of mathematics studies » (n^o 34), 1956 (MR 0078059), p. 129–153.
• John Hopcroft, « An n log n algorithm for minimizing states in a finite automaton », dans Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York, Academic Press, 1971 (MR 0403320), p. 189–196

Manuels

• Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, p. 157–162 (Chapitre 4.13 Partitioning).
• Jean Berstel, Luc Boasson, Olivier Carton et Isabelle Fagnot, « Minimization of Automata », dans Automata: from Mathematics to Applications, European Mathematical Society, 2010 (arXiv 1010.5318)
• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)
• Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, 2003, 816 p. (ISBN 2-7117-4807-3, zbMATH 1188.68177)
• Patrice Séébold, Théorie des automates : Méthodes et exercices corrigés, Vuibert, 1999, 198 p. (ISBN 978-2-7117-8630-5)
• Peter Linz, An Introduction to Formal Languages and Automata, Sudbury, MA, Jones & Bartlett Publishers, 2011, 5^e éd., 437 p. (ISBN 978-1-4496-1552-9, lire en ligne).

Autres références

• Cezar Câmpeanu, Karel Culik II, Kai Salomaa et Sheng Yu, « State Complexity of Basic Operations on Finite Languages », dans 4th International Workshop on Automata Implementation (WIA '99), Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 2214), 2001 (DOI 10.1007/3-540-45526-4_6), p. 60–70.
• Ernst Leiss, « Succinct representation of regular languages by Boolean automata », Theoretical Computer Science, vol. 13, n^o 3,‎ 1981, p. 323–330 (DOI 10.1016/S0304-3975(81)80005-9, MR 603263).
• Sven De Felice et Cyril Nicaud, « Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata », dans Marie-Pierre Béal et Olivier Carton (éditeurs), Developments in Language Theory - 17th International Conference, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 7907), 2013 (ISBN 978-3-642-38770-8, DOI 10.1007/978-3-642-38771-5_17), p. 179-190
• Tsunehiko Kameda et Peter Weiner, « On the state minimization of nondeterministic finite automata », IEEE Transactions on Computers, vol. 100, n^o 7,‎ 1970 (DOI 10.1109/T-C.1970.222994).
• Timo Knuutila, « Re-describing an algorithm by Hopcroft », Theoretical Computer Science, vol. 250, n^os 1-2,‎ 2001, p. 333–363 (DOI 10.1016/S0304-3975(99)00150-4, MR 1795249).
• (en) Norbert Blum, « An O(n log n) implementation of the standard method for minimizing n-state finite automata », Information Processing Letters, vol. 57, n^o 2,‎ 1996, p. 65–69 (DOI 10.1016/0020-0190(95)00199-9).
• (en) David Gries, « Describing an algorithm by Hopcroft », Acta Informatica, vol. 2, n^o 2,‎ 1973, p. 97-109 (DOI 10.1007/BF00264025).