Abstract FR:

L'objet de cette these est l'etude des relations sur les mots finis ou infinis, definies par transducteur (ou automate avec sortie). Les automates sont des machines abstraites utilisees pour modeliser des systemes reagissant a des suites d'instructions representees par des mots (chaque instruction etant representee par une lettre). Un transducteur est un automate qui, pour chaque operation effectuee, produit une ou plusieurs informations. Il definit ainsi une relation (qu'on appellera rationnelle) entre les mots d'entree (instructions) et les mots de sortie (informations produites). Les suites d'instructions ou d'informations lues ou produites par un transducteur peuvent etre infinies, si le systeme modelise n'est pas suppose s'arreter (chaine de montage, systeme d'exploitation d'un ordinateur, etc. ). Si la notion de transducteur est apparue dans les annees 50 avec celle d'automate, et si d'autre part, l'etude des automates de mots infinis, nee des preoccupations de logiciens tels buchi et landweber, date des annees 60, ce n'est qu'au debut des annees 80 que gire et nivat ont introduit les transducteurs de mots infinis, extension qui semble naturelle, mais pose de nombreux problemes. L'utilisation pratique des mots infinis necessite de pouvoir travailler sur des prefixes de ces mots et passe souvent par une etude topologique des ensembles consideres. En particulier, la possibilite de calculer l'image d'un mot au fur et a mesure qu'on le lit est tres liee a la notion de continuite d'une fonction. En plus de certains resultats sur les fonctions sequentielles de mots finis, l'objectif de cette these est la mise au point d'algorithmes pour decider la continuite des fonctions rationnelles de mots infinis. Les differentes etapes sont l'etude topologique des relations rationnelles de mots infinis (en particulier le calcul de la fermeture d'une relation), ainsi que la mise au point de divers algorithmes sur les transducteurs de mots finis ou infinis (decider si un transducteur definit une fonction, une fonction synchrone, calculer les etats constants d'un automate, etc. ).