Gestion de ressources des transductions régulières sur les mots

Abstract

Cette thèse a eu pour objectif d'étudier des questions naturelles de définissabilité autour des transducteurs bidirectionnels.Il est bien connu que les transducteurs bidirectionnels définissent une plus grande classe de transductions que celles des transducteurs unidirectionnels. La première question que nous avons étudiée est donc de décider si un transducteur bidirectionnel est définissable par un transducteur unidirectionnel. Il a été montré en 2013 que cette question est décidable pour des transducteurs fonctionnels (nous montrons aussi en paralèlle que cette question devient indécidable si les transducteurs ne sont plus fonctionnels) mais la complexité de la procédure de décision était non-élémentaire.Nous proposons une caractérisation de la "définissabilité par transducteur unidirectionnel" décidable en espace doublement exponentiel. Cette caractérisation est effective en ce sens qu'elle produit en temps triplement exponentiel le transducteur équivalent. De plus, nous avons étudié ce problème aussi pour les transducteurs "sweeping", pour lesquels la procédure de décision et la construction du transducteur équivalent requièrent une exponentielle de moins. Comme nous avons par ailleurs montré qu'il existe des familles de fonctions réalisables de façon unidirectionnelle avec au minimum deux sauts exponentiels, notre procédure est optimale dans le cas "sweeping".Le fait d'avoir particulièrement étudié les transducteurs"sweeping" nous a poussé à étudier d'autres questions dedéfinissabilité~: est-ce qu'un transducteur donné estréalisable par un transducteur sweeping ? Et par un transducteursweeping réalisant au maximum k passages ? Nous montrons que cesquestions sont décidables avec les mêmes complexitésobtenues précédemment. Comme nous avons montré qu'ilexiste une borne sur le nombre de passages nécéssaires pourréaliser avec un transducteur sweeping une transductiondonnée, cela nous permet aussi de minimiser le nombre de passages d'untransducteur sweeping.Enfin nous avons cherché à caractériser la classe destransductions sweeping dans d'autres modèles de transductions,les Streaming String Transducers (SST) et lestransductions MSO. Cela a en autres permis, en établissant unecorrespondance entre le nombre de passages des transducteurssweeping et le nombre de registres d'une sous-classe de SST, deminimiser le nombre de registres pour une classe intéressantede SST. Dans l'ensemble, notre travail a permis de couvrir l'ensembledes relations entre ces modèles, et les questions dedéfinissabilité qui se posent naturellement.