Skip to Main content Skip to Navigation
Conference papers

On the Average Complexity of Moore's State Minimization Algorithm

Abstract : We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with n states, the average complexity of Moore's state minimization algorithm is in O(n log n). Moreover this bound is tight in the case of unary utomata.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Friday, February 6, 2009 - 10:35:36 AM
Last modification on : Wednesday, January 19, 2022 - 4:42:04 PM
Long-term archiving on: : Thursday, June 30, 2011 - 10:50:23 AM


Files produced by the author(s)


  • HAL Id : inria-00359162, version 1
  • ARXIV : 0902.1048


Frédérique Bassino, Julien David, Cyril Nicaud. On the Average Complexity of Moore's State Minimization Algorithm. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.123-134. ⟨inria-00359162⟩



Record views


Files downloads