Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620346
Contributor : Julien David <>
Submitted on : Friday, September 30, 2011 - 4:28:30 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
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⟩

Share