Résumé : Dans un premier temps, on présentera une méthode de génération aléatoire d’automates déterministes accessibles complets et un outil, REGAL, utilisant cette méthode. Les générateurs implantés dans REGAL permettent d’engendrer des automates de plusieurs milliers d’états et ce faisant, d’établir des conjectures crédibles sur les propriétés en moyenne des automates, ainsi que sur les algorithmes qui s’y appliquent. Dans une deuxième partie, on présentera un résultat théorique sur la complexité moyenne de l’algorithme de Moore: si la complexité dans le pire cas de l’algorithme est connu pour être en $\mathcal{O}(n^2)$, on montrera que pour un alphabet fini arbitraire et la distribution uniforme sur l’ensemble des automates déterministes accessibles complets n états, la complexité moyenne est $\mathcal{O}(n\log n)$.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr