On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

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

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

Dates et versions

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

Identifiants

Citer

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/978-3-319-09698-8_3⟩. ⟨hal-01772856⟩
63 Consultations
142 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More