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.
| Dernière modification : Monday 27 May 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |