Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 11 Juin 2013

Des transducteurs bidirectionnels aux transducteurs unidirectionnels

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr