Brzozowski Algorithm Is Generically Super-Polynomial Deterministic Automata

Abstract : We study the number of states of the minimal automaton of the mirror of a rational language recognized by a random deterministic automaton with n states. We prove that, for any d > 0, the probability that this number of states is greater than nd tends to 1 as n tends to infinity. As a consequence, the generic and average complexities of Brzozowski minimization algorithm are super-polynomial for the uniform distribution on deterministic automata.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00841848
Contributor : Cyril Nicaud <>
Submitted on : Saturday, July 6, 2013 - 1:17:18 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Monday, October 7, 2013 - 2:35:12 AM

File

Brzozowski_Algorithm_Is_Generi...
Files produced by the author(s)

Identifiers

Citation

Sven de Felice, Cyril Nicaud. Brzozowski Algorithm Is Generically Super-Polynomial Deterministic Automata. DLT'13, 2013, France. pp.179-190, ⟨10.1007/978-3-642-38771-5_17⟩. ⟨hal-00841848⟩

Share

Metrics

Record views

321

Files downloads

225