| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [18 references]
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
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)