Average Case Analysis of Brzozowski's Algorithm - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue International Journal of Foundations of Computer Science Année : 2016

Average Case Analysis of Brzozowski's Algorithm

Résumé

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

Dates et versions

hal-01772820 , version 1 (20-04-2018)

Identifiants

Citer

Sven de Felice, Cyril Nicaud. Average Case Analysis of Brzozowski's Algorithm. International Journal of Foundations of Computer Science, 2016, 27 (02), pp.109-126. ⟨10.1142/S0129054116400025⟩. ⟨hal-01772820⟩
45 Consultations
199 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More