by Jean Berstel and Olivier Carton
L'algorithme de Hopcroft pour la minimisation d'un automate déterministe a une complexité de O(n log n). Nous montrons que cette borne est atteinte. Plus précisément, nous donnons une famille d'automates de tailles n = 2k sur lesquels l'algorithme fonctionne en temps k2k. Ces automates ont une structure très simple et sont sur un alphabet à une lettre. Leurs états finaux sont définis par des mots de de Bruijn.
Hopcroft's algorithm for minimizing a deterministic automaton has complexity O(n log n). We show that this complexity bound is tight. More precisely, we provide a family of automata of size n = 2k on which the algorithm runs in time k2k. These automata have a very simple structure and are built over a one-letter alphabet. Their sets of final states are defined by de Bruijn words.
Pdf of version presented at the conference CIAA'2004 in Kingston, Ontario, Canada.