Il s'agit de mon Habilitation à Diriger des Recherches soutenue le vendredi 14 décembre 2001 à l'université de Marne-la-Vallée devant le jury constitué de
Depuis le début de mon doctorat, le thème central de mes recherches à été l'étude des automates sur des objets infinis tels que les mots infinis, les mots bi-infinis ou même les mots transfinis.
La théorie des automates a des liens étroits avec nombre de domaines aussi bien en informatique qu'en mathématiques. Il existe en effet des connexions avec l'algorithmique, la théorie de la complexité, la logique, la combinatoire, la théorie des jeux, l'algèbre, la topologie, la théorie descriptive, les systèmes dynamiques et la théorie des nombres. Cette diversité des interactions est bien reflétée par les différents aspects abordés dans mes recherches. Lors de mon doctorat déjà, j'avais étudié la hiérarchie de Wagner qui établit des liens entre des classes topologiques et des automates. Mes travaux en collaboration avec Marie-Pierre Béal sur les transducteurs et la méthode de calcul de l'indice de Rabin développée avec Ramón Maceiras sont de nature algorithmique. Dans l'étude des automates sur les mots transfinis, nous avons utilisé, avec Nicolas Bedon, des outils algébriques. Finalement, les prédicats morphiques abordés en collaboration avec Wolfgang Thomas concernent des questions de logique.
Ce document comporte quatre parties. Au prix de quelques redites, les parties sont indépendantes. La première partie est une introduction aux automates à l'usage des néophytes.
La seconde partie est consacrée à des travaux concernant les automates sur les mots infinis. Elle regroupe les résultats de trois collaborations sur des thèmes assez différents avec Ramón Maceiras, Max Michel et Wolfgang Thomas. Les résultats obtenus avec Ramón Maceiras sont de nature algorithmique. Ils concernent le calcul de l'indice de Rabin d'un ensemble de mots infinis donné par un automate à parité. L'objet des travaux avec Max Michel est l'étude d'une classe particulière d'automates de Büchi appelés non-ambigus. Le résultat principal s'apparente à un théorème de McNaughton pour les automates co-déterministes. Finalement, la collaboration avec Wolfgang Thomas a conduit à des résultats de décidabilité de certaines logiques. Il s'agit en quelque sorte d'un retour aux sources puisque ce sont ces mêmes questions de décidabilité qui avaient conduit Büchi à introduire les automates sur les mot infinis.
La troisième partie regroupe des travaux sur la dynamique symbolique et les transducteurs. Le premier résultat a été obtenu en collaboration avec Marie-Pierre Béal et Christophe Reutenauer. Il s'agit d'une décomposition des langages cycliques en langages de stabilisateurs qui conduit à une nouvelle preuve de la rationalité de la fonction zêta d'un langage cyclique. Les deux autres résultats ont été obtenus en collaboration avec Marie-Pierre Béal. Le premier concerne la synchronisation de transducteurs sur des mots bi-infinis, et le second la déterminisation de transducteurs sur des mots infinis.
La quatrième et dernière partie est consacrée à des extensions de la notion de mots infinis et d'automates. Les résultats obtenus en collaboration avec Nicolas Bedon concernent les mots transfinis et les automates introduits par Büchi. Notre contribution essentielle est d'avoir développé une théorie algébrique de ces mots. Nous avons obtenu un théorème de variétés qui étend celui d'Eilenberg. Nos résultats redonnent en particulier une autre preuve de la déterminisation des automates. Finalement, les travaux avec Véronique Bruyère ont étendu ces automates sur les mots transfinis à des automates sur des ordres linéaires. Le résultat principal est une extension du théorème de Kleene aux ordres dispersés et dénombrables.