Brzozowski Algorithm Is Generically Super-Polynomial Deterministic Automata - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Brzozowski Algorithm Is Generically Super-Polynomial Deterministic Automata

Résumé

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.
Fichier principal
Vignette du fichier
Brzozowski_Algorithm_Is_Generically_Super-Polynomial_Deterministic_Automata.pdf (179.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00841848 , version 1 (06-07-2013)

Identifiants

Citer

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⟩
169 Consultations
381 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More