16/10/2008 Jean-Éric Pin (LIAFA, Paris)

Dualité et théorie équationnelle des langages rationnels

Je présenterai un nouveau résultat sur la théorie équationnelle des langages rationnels, obtenu à la suite de discussions animées entre les auteurs sur les dualités de Stone et de Priestley. Appelons `treillis de langages' une classe de langages rationnels fermée par intersection finie et union finie. Les résultats principaux que je présenterai peuvent être résumés ainsi:

Un ensemble de langages rationnels est un treillis de langages si et seulement si il peut être défini par un ensemble d'équations profinies.

Le produit des mots profinis est le dual de l'opération de résiduation sur les langages rationnels.

Vous vous demandez ce veut dire "profini" ? On peut obtenir l'espace des mots profinis soit comme complété de l'espace des mots finis muni d'une certaine métrique, soit comme dual (au sens de Stone) du treillis des langages rationnels. Mais j'en dirai plus pendant l'exposé... [travail en collaboration avec Mai Gehrke et Serge Grigorieff]