Cyril Nicaud (Institut Gaspard Monge, Université de Paris Est)

Les langages rationnels et les automates finis sont des objets qui interviennent souvent en informatique, aussi bien théorique qu’appliquée. Il existe donc beaucoup d’algorithmes qui les manipulent. Leurs complexités dans le pire des cas sont bien connues ; l’objet de cet exposé est de présenter des résultats récents obtenus pour le cas moyen. J’en profiterai pour présenter rapidement les principaux outils utilisés, qui proviennent principalement de la combinatoire analytique.