Evènement pour le groupe Séminaire du LaBRI


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.  
LieuAmphithéâtre du LaBRI (050) 
OrateurFrédérique Bassino 
EmailFrederique.Bassino@lipn.univ-paris13.fr 
UrlLaboratoire d'Informatique de l’université Paris-Nord (LIPN) 



Aucun document lié à cet événement.

Retour
Retour à l'index