|
Evènement pour le groupe Graphes et Logique
Date | 2013-11-26 11:00-12:00 |
Titre | Systè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é!
|
Lieu | salle 076 |
Orateur | Yves Roos |
Email | yves.roos@lifl.fr |
Url | LILF, Université des Sciences et Technologies de Lille |
Aucun document lié à cet événement. RetourRetour à l'index
| |