Résumé : Cet exposé portera sur la génération aléatoire d’automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l’ensemble respectivement des états initiaux et des états finals). On présentera une bijection entre l’ensemble des automates déterministes et accessibles à n états sur un alphabet fini et des diagrammes particuliers qui peuvent eux-mêmes être représentés comme les partitions d’un ensemble en n sous ensembles non-vides. Ces constructions combinatoires permettent d’estimer asymptotiquement le nombre d’automates à n états. Cette approche combinatoire a conduit à la conception d’un générateur aléatoire efficace, pour la distribution uniforme sur les automates déterministes à n états : la complexité moyenne en temps du générateur de Boltzmann associé est en O(n3/2). On montrera quelques exemples de résultats expérimentaux obtenus avec la librairie C++ REGAL dans laquelle il est implanté. [ Travail en collaboration avec Julien David et Cyril Nicaud (IGM). ]
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |