The Average Complexity of Moore's State Minimization Algorithm is $O( n \log \log n)$

Julien David (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We prove that the average complexity, for the uniform distribution on complete deterministic automata, of Moore's state minimization algorithm is O(n log log n), where n is the number of states in the input automata.

Domaines: Algorithme et structure de données [cs.DS]

Julien David. The Average Complexity of Moore's State Minimization Algorithm is $O( n \log \log n)$. 35th International Symposium on Mathematical Foundations of Computer Science, Aug 2010, Faculty of Informatics, Masaryk University, Botanicka, 60200 Brno, Czech Republic. pp.318-329. ⟨hal-00620346⟩