Inès Klimann (LIAFA, Paris 7)

Un état d’un transducteur lettre-à-lettre (automate avec entrée et sortie) peut, sous certaines conditions, induire une fonction de l’ensemble des mots sur un alphabet dans lui-même. En composant les fonctions ainsi obtenues entre elles, on peut engendrer un semi-groupe, voire un groupe.

Je commencerai par évoquer deux problèmes classiques de théorie des groupes, liés à la façon dont un groupe croît à partir de la donnée d’un ensemble fini de génerateurs: le problème de Burnside et le problème de Milnor.

Le premier de ses problème a reçu plusieurs réponses, mais les plus élégantes, sans le moindre doute, sont données par des groupes engendrés par des automates. Quant au deuxième problème, on ne sait à ce jour y répondre que par de tels groupes.

Je montrerai le cas étonnant des semi-groupes engendrés par des automates à 2 états: ils sont soit finis, soit libres; ce qui a des conséquences pour les deux problèmes cités précédemment.