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

https://hal.inria.fr/inria-00359162
Contributor : Publications Loria <>
Submitted on : Friday, February 6, 2009 - 10:35:36 AM
Last modification on : Wednesday, February 3, 2021 - 7:54:26 AM
Long-term archiving on: : Thursday, June 30, 2011 - 10:50:23 AM

Files

bassino_new.pdf
Files produced by the author(s)

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

479

Files downloads

311