Les automates (DFA) sont des machines à états qui acceptent ou rejettent des mots. L’ensemble des mots reconnus par un automate est son langage. Les langages rationnels coïncident avec les langages reconnaissable par des automates. Ici nous allons nous intéresser à une mesure, à savoir la complexité en états. Sur les langages rationnels elle est définie comme la taille du plus petit automate (déterministe) qui reconnait le langage. Sur les opérations, elle est définie comme l’action d’une opération sur les automates minimaux des langages rationnels.
Les opérations racine et renversé sont des opérations bien connues. Leur complexité en états est respectivement n^n – n(n-1)/2 et 2^n. On pourrait s’attendre à une explosion du nombre d’états lorsqu’on les compose.
L’enjeu de ce séminaire sera d’établir toutes les bases nécessaires à la compréhension du problème, puis de montrer que non seulement la composition racine-renversé ne produit pas d’explosion combinatoire mais en fait produit un automate plus petit que celui de la racine dans les pires cas.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne