On the Complexity of Hopcroft’s State Minimization Algorithm

@incollection{citeulike:2137702, abstract = {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 = 2 k on which the algorithm runs in time  k2 k. 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.}, author = {Berstel, Jean and Carton, Olivier }, citeulike-article-id = {2137702}, journal = {Implementation and Application of Automata}, pages = {35--44}, posted-at = {2008-02-24 00:52:18}, priority = {2}, title = {On the Complexity of Hopcroft’s State Minimization Algorithm}, url = {http://www.springerlink.com/content/v50r50kt05jlxxv4 }, year = {2005} }

TY - CHAP ID - citeulike:2137702 L3 - citeulike-article-id:2137702 TI - On the Complexity of Hopcroft’s State Minimization Algorithm JF - Implementation and Application of Automata SP - 35 EP - 44 N2 - 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 = 2 k on which the algorithm runs in time  k2 k. 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. AU - Berstel, Jean AU - Carton, Olivier PY - 2005/// UR - http://www.springerlink.com/content/v50r50kt05jlxxv4 ER -