 |
HAL UPEC - UPEM Portal |  |
 |
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.
Cited literature [9 references]
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
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)