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

Abstract : 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.
Document type :
Conference papers

Cited literature [9 references]

https://hal-upec-upem.archives-ouvertes.fr/hal-00620346
Contributor : Julien David Connect in order to contact the contributor
Submitted on : Friday, September 30, 2011 - 4:28:30 PM
Last modification on : Tuesday, October 19, 2021 - 11:25:54 AM
Long-term archiving on: : Saturday, December 31, 2011 - 2:20:42 AM

### File

hal.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00620346, version 1

### Citation

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⟩

Record views