10 mars 2014
Ines Klimann (LIAFA - Université Paris-Diderot)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 montrer la construction faite par Pierre Gillibert pour montrer que dans le cas général la finitude des semi-groupes d’automate est un problème indécidable.
La question reste ouverte dans le cas des groupes. Je montrerai quelle réponse on peut apporter pour la sous-famille des groupes engendrés par des automates inversibles-réversibles sur 2 lettres.