Olivier Gauwin (LaBRI, Bordeaux)

Tout automate bidirectionnel est équivalent à un automate unidirectionnel. Ce résultat, établi par Rabin et Scott et indépendamment par Shepherdson, montre que les automates bidirectionnels (y compris non-déterministes) caractérisent la classe des langages réguliers. Il est également connu que ce résultat ne s’étend pas aux transducteurs : les transducteurs bidirectionnels (déterministes) sont strictement plus expressifs que les transducteurs unidirectionnels (fonctionnels). En particulier les transducteurs bidirectionnels déterministes capturent exactement les transductions MSO de mots finis. Dans cet exposé nous considérerons la question suivante : étant donné un transducteur bidirectionnel fonctionnel, existe-t-il un transducteur unidirectionnel équivalent ? En étendant la preuve de Rabin et Scott, nous montrerons que ce problème est décidable. Ce résultat est issu d’un travail commun avec Emmanuel Filiot, Pierre-Alain Reynier et Frédéric Servais.