Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Sur les langages de triplets de mots
du 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