On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States

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. We therefore go beyond the previous study where the number of final states was linear in the number of states. Our result holds for alphabets with at least 3 letters.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-01772856
Contributor : Admin Upem <>
Submitted on : Friday, April 20, 2018 - 4:05:22 PM
Last modification on : Thursday, July 5, 2018 - 2:46:10 PM
Long-term archiving on : Tuesday, September 18, 2018 - 6:01:42 PM

File

dlt14.pdf
Files produced by the author(s)

Identifiers

Citation

Sven de Felice, Cyril Nicaud. On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States. DLT 2014, Aug 2014, Ekaterinburg, Russia. pp.25-36, ⟨10.1007%2F978-3-319-09698-8_3⟩. ⟨hal-01772856⟩

Share

Metrics

Record views

90

Files downloads

88