Evènement pour le groupe Graphes et Logique


Date 2013-11-26  11:00-12:00
TitreSystèmes de réécriture (de mots) à une règle préservant les longueurs et transductions rationnelles 
RésuméL'exposé présentera quelques avancées concernant la question suivante : étant donné un système de réécriture S à une règle u -> v où les mots u et v sont distincts et de même longueur, comment décider si la transformation, qui à tout mot w fait correspondre l'ensemble S(w) des mots qu'on peut obtenir à partir de w en itérant l'application de la règle u -> v, définit une transduction rationnelle? L'un des exemples négatifs parmi les plus simples est clairement le système S = {ab -> ba}. En revanche, le système S = {abb -> baa} définit, lui, une transduction rationnelle. Dans cet exposé, on répond partiellement à une conjecture (maintenant ancienne!) portant sur une caractérisation simple des systèmes S = { u -> v } définissant une transduction rationnelle. On y présentera aussi les questions ouvertes que ces travaux ont engendrées dont une caractéristique commune est la simplicité de leur énoncé!  
Lieusalle 076 
OrateurYves Roos 
Emailyves.roos@lifl.fr 
UrlLILF, Université des Sciences et Technologies de Lille 



Aucun document lié à cet événement.

Retour
Retour à l'index