LRDE Seminar: 22 Juin 2005, Vaucanson, EPITA, Amphi P004

14h00 : Des automates de couverture de langages finis -- Michaël Cadilhac^?

Bien que les langages rationnels et les automates finis soient énormément utilisés et étudiés, beaucoup d'utilisations ne se consacrent qu'aux langages finis. Un automate de couverture pour un langage fini accepte tous les mots du langage, mais aussi des mots plus longs que le mot le plus long du langage.

Construire un automate de couverture d'un langage fini conduit à la création d'un automate pouvant avoir un nombre d'états significativement réduit par rapport à l'automate reconnaissant strictement le langage.

Nous présenterons la théorie des automates de couverture, et parlerons en particulier des automates de couverture déterministes minimaux et des algorithmes permettant de les trouver. Enfin, nous étudierons l'efficacité de ces derniers en terme de complexité et d'utilisation mémoire.

14h45 : Méthodes de calcul du langage rationnel reconnu par un automate -- Robert Bigaignon^?

Le théorème de Kleene nous a apporté depuis longtemps la preuve qu'un automate fini reconnaît un langage rationnel. Ainsi, certaines méthodes nous permettent de calculer, à partir de l'automate, une expression rationnelle dénotant ce langage.

Nous étudierons, lors de ce séminaire, différentes méthodes en comparant leur efficacité et nous envisagerons l'application d'heuristiques pour certaines d'entre elles. Nous finirons par l'implémentation des méthodes les plus pertinentes au sein de Vaucanson, la bibliothèque de manipulation d'automates finis développée par le LRDE.

15h45 : De son expression à l'automate -- Florent Terrones^?

Si l'on obtient une expression rationnelle correspondant au langage reconnu par un automate co-minimal, il est parfois possible de retrouver l'automate de départ grâce à une version légèrement modifiée de l'algorithme des termes dérivés. Si c'est le cas, on peut y trouver des applications intéressantes. Sinon, on peut faciliter la recherche d'une solution grâce à l'implémentation d'outils dans Vaucanson.

Dans ce séminaire, un point sera fait sur les cas pour lesquels il est possible de retrouver l'automate initial, et sur les possibilités qu'offre un tel résultat. Puis une étude sera faite sur les axes de recherche actuels afin de retrouver l'automate originel pour les cas problématiques. Enfin, pour chacun d'entre eux, on expliquera en quoi Vaucanson peut apporter de l'aide.
to top