Date | 2014-10-02 10:00-11:00 |
Titre | Énumération asymptotique d'automates finis |
Résumé | Cet exposé portera sur l'énumération 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 terminaux). Les automates (resp. minimaux) constituent une représentation (resp. canonique) des langages rationnels et de ce fait jouent un rôle important en informatique.
Nous présenterons des résultats concernant l'énumération des automates déterministes et accessibles, i. e. dans lesquels tout état peut-être atteint par un chemin partant de l'unique état initial. Nous déterminerons ensuite précisément la proportion asymptotique d'automates minimaux parmi les automates déterministes accessibles et complets. Ces résultats ont des conséquences en terme de complexité en moyenne d'algorithmes.
Toutes ces estimations peuvent être obtenues grâce à une interprétation combinatoire des propriétés structurelles des automates et à des bijections qui permettent de se ramener à l'étude combinatoire de tableaux particuliers.
Nous conclurons en présentant quelques problèmes ouverts.
Cet exposé s'appuie sur une série de travaux communs avec Julien David, Cyril Nicaud et Andrea Sportiello. |
Lieu | Amphithéâtre du LaBRI (050) |
Orateur | Frédérique Bassino |
Email | Frederique.Bassino@lipn.univ-paris13.fr |
Url | Laboratoire d'Informatique de l’université Paris-Nord (LIPN) |
Aucun document lié à cet événement.