Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 22 mars 2011 à 14h00 en B311, Laura Giambruno nous parlera de : Étude de la complexité en états moyenne des opérations rationnelles sur les langages finis

Résumé : La complexité en états d'un langage rationnel est le nombre d'états de son automate minimal. Dans cet exposé nous considèrerons une distribution, où les langages finis sont donnés comme une liste de mots, et nous étudierons la complexité en moyenne des opérations rationnelles: union, concaténation et étoile. L'étude en moyenne est particulièrement intéressante quand le pire de cas est exponentiel, ce qui est le cas ici pour l'étoile et pour la concaténation. Nous prouverons notamment qu'en moyenne la complexité est de ces deux opérations est linéaire. Nous finirons l'exposé en présentant une extension de ces résultats à d’autres classes de langages. Il s'agit de travaux effectués en collaboration avec F. Bassino et C. Nicaud.

 [Slides.pdf]


Dernière modification : mercredi 06 juillet 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr