Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Cyril Nicaud Connect in order to contact the contributor
Submitted on : Saturday, July 6, 2013 - 1:17:18 PM
Last modification on : Saturday, January 15, 2022 - 3:58:47 AM
Long-term archiving on: : Monday, October 7, 2013 - 2:35:12 AM


Files produced by the author(s)



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⟩



Record views


Files downloads