Evènement pour le groupe Graphes et Logique


Date 2011-11-15  11:00-12:00
TitreSur les langages de triplets de mots 
RésuméOn s'intéresse aux langages de triplets de mots finis de la forme (u1,u2,u3) qui ont pour vocation à représenté des mots «contextualisés». Plus précisément, le triplet de mot (u1,u2,u3) représente le mot u2 dont l’usage est restreint à un certain contexte d’utilisation définit par u1 et u3 de la façon suivante : un tel mot ne peut être concaténé, à gauche, que par un mot finissant par u1 et à droite, que par un mot commençant par u3. L'étude de ce modèle, apparemment ad hoc, et du produit (partiel) qu’il induit, nous conduit cependant à la définition d’une extension originale du monoïde libre qui semble répondre à une question de Jean-Camille Birget en 1992 : quelle structure algébrique correspond aux automates boustrophédons (ou two way automata). En développant cette théorie, on obtient en particulier, pour les langages de triplets : - d’une notion d'automate boustrophédons déterministe canonique (minimal ?), - d’une notion d'expression rationnel, - d’une notion algébrique de reconnaissabilité, toutes trois équivalentes. La théorie obtenue, qui poursuit les travaux de Rabin et Scott (1959), Shepherdson (1959), Pecuchet (1985), Birget (1989), et de nombreux autres (e.g. Vardi, 1989, Hines 1997), se révèle tout à la fois simple, conséquente et solide. Elle semble ouvrir de nombreuses perspectives aussi bien en algèbre : quelle structure algébrique générique sous-jacente à ce monoid des triplets ? en théorie des automates : quelles liens avec les pebbles two-way automata ? et, en plongeant les mots dans les mots temporisés : quelles expressions algébriques induites pour les langages temporisés ? 
Lieusalle 76 
OrateurDavid Janin 
Emaildavid.janin@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index