Complexité en états : Renverser un langage réduit la complexité de l'opération racine.
Time: 14:00 -- Location: LRI, 445
summary: 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.