Skip to Main content Skip to Navigation
Journal articles

Average Case Analysis of Brzozowski's Algorithm

Abstract : We analyze the average complexity of Brzozowski's minimization algorithm for distributions of deterministic automata with a small number of final states. We show that, as in the case of the uniform distribution, the average complexity is super-polynomial even if we consider random deterministic automata with only one final state. Such results were only known for distributions where the expected number of final states was linear in the number of states.
Document type :
Journal articles
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01772820
Contributor : Admin Upem <>
Submitted on : Friday, April 20, 2018 - 3:59:27 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Long-term archiving on: : Tuesday, September 18, 2018 - 5:59:30 PM

File

ijfcs16.pdf
Files produced by the author(s)

Identifiers

Citation

Sven de Felice, Cyril Nicaud. Average Case Analysis of Brzozowski's Algorithm. International Journal of Foundations of Computer Science, World Scientific Publishing, 2016, 27 (02), pp.109-126. ⟨10.1142/S0129054116400025⟩. ⟨hal-01772820⟩

Share

Metrics

Record views

130

Files downloads

297