February 13, 2012
Olivier Carton (LIAFA)Dans cet exposé, on considère des transducteurs bidirectionnels à bande de sortie bidirectionnelle. À chaque cellule de la bande d’entrée correspond une cellule de la bande de sortie. À chaque transition, le transducteur lit une cellule de la bande d’entrée et soit laisse inchangé la cellule correspondant de la bande de sortie ou écrit un mot qui remplace le contenu précédent. Nous montrons que chaque relation réalisée par un tel transducteur est rationnelle. Elle peut être réalisée par un transducteur de gauche à droite. Nous montrons également que toute fonction rationnelle peut être réalisée par un transducteur bidirectionnel déterministe.