10.4230/LIPICS.STACS.2009.1822
Bassino, Frederique
Frederique
Bassino
David, Julien
Julien
David
Nicaud, Cyril
Cyril
Nicaud
On the Average Complexity of Moore's State Minimization Algorithm
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Article
Finite automata
State minimization
Moore’s algorithm
Average complexity
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
2009
2009-02-19
2009-02-19
2009-02-19
en
urn:nbn:de:0030-drops-18222
10.4230/LIPIcs.STACS.2009
978-3-939897-09-5
1868-8969
10.4230/LIPIcs.STACS.2009
LIPIcs, Volume 3, STACS 2009
26th International Symposium on Theoretical Aspects of Computer Science
2013
3
9
123
134
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
3
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
204563 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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 $\mathcal{O}(n \log n)$. Moreover this bound is tight in the case of unary automata.
LIPIcs, Vol. 3, 26th International Symposium on Theoretical Aspects of Computer Science, pages 123-134