Ali Akhavi (GREYC, Caen)

Les états d’un transducteur lettre à lettre définissent chacun naturellement une fonction de l’ensemble des mots de l’alphabet d’entrée/sortie vers lui- même (conservant la longueur et les préfixes). Ils engendrent ainsi un semi- groupe: le semi-groupe engendré par le transducteur. Si chaque état définit une permutation de l’alphabet d’entrée/sortie dans lui-même (transducteur inversible), on peut parler aussi du groupe engendré par le transducteur.

Les groupes ainsi définis sont d’un grand intérêt, notamment par leur contribution à des problèmes célèbres de la théorie combinatoire des groupes: Il a été exhibé des exemples particulièrement simples de transducteurs engendrant des groupes infinis de torsion (problème de Burnside) ou des groupes à croissance intermédiaire (problème de Milnor). Parmi les questions (souvent difficiles) classiques en théorie combinatoire des (semi)groupes se pose celle de la finitude: Etant donné un transducteur lettre à lettre, le (semi) groupe qu’il engendre est-il fini?

Nous apportons des éléments de réponses à cette question: un critère effectif suffisant de finitude, un critère effectif nécessaire de finitude et un critère nécessaire et suffisant, mais non effectif de finitude. Notre expérimentation montre que notre contribution permet de répondre à la question de la finitude dans de très nombreux cas où les méthodes antérieures échouaient.