Automate fini, Transducteur fini, Transducteur bidirectionnel, Transducteur à jetons, Transducteur à registres, Fonction rationnelle, Fonction régulière, Fonction polyrégulière, Problème d'appartenance à une classe, Optimisation de programmes

Les transducteurs sont des machines à états finis qui calculent des fonctions (ou des relations) des mots vers les mots. Ils peuvent être considérés comme des programmes dont la mémoire est limitée et qui manipulent des chaînes de caractères. Ces machines ont été étudiées depuis longtemps en informatique fondamentale, au sein de la théorie des automates, et sont utilisées dans de nombreux domaines comme la compilation, le traitement des langages naturels, ou le traitement des flux de données. Dans la littérature, de nombreux modèles de transducteurs ont été définis grâce à des fonctionnalités qui permettent d'augmenter l'expressivité des machines (comme le non-déterminisme, la bidirectionnalité ou l'imbrication). Dans ce contexte, une question naturelle est celle de l'appartenance à une classe : étant donnée une fonction calculée par un transducteur avec des fonctionnalités "complexes", peut-on la calculer par un transducteur "plus simple" ? Certains de ces problèmes ont déjà été résolus, et ils sont en général considérés comme difficiles. D'un point de vue pratique, ils s'interprètent comme des questions d'optimisation de programmes : étant donné un programme qui utilise beaucoup de ressources, peut-on construire un programme équivalent qui est "plus efficace" ? Cette thèse propose de résoudre plusieurs problèmes d'appartenance entre des classes de transductions existantes, à la fois sur les mots finis et infinis. Les modèles bien connus de transducteurs bidirectionnels et de transducteurs à jetons sont notamment étudiés. À chaque fois, la procédure d'appartenance est non triviale, et elle s'avère effective (dans le sens où elle construit un transducteur "plus simple" dès qu'il en existe un). C'est pourquoi les résultats de ce manuscrit peuvent être vus comme des techniques d'optimisation de programmes. En outre, nous résolvons ces problèmes par une méthode générique basée sur l'utilisation de propriétés sémantiques (c'est-à-dire qui parlent intrinsèquement des fonctions) et syntaxiques (qui parlent des transducteurs qui calculent ces fonctions). Enfin, cette thèse fournit de nouveaux modèles et de nouvelles caractérisations pour décrire des classes de transductions connues. Ces résultats améliorent et complètent la compréhension de ces classes. L'auteur est convaincu que les différentes techniques développées dans ce manuscrit fournissent une boîte à outils pour étudier d'autres problèmes d'appartenance, qui sont encore ouverts.