Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 17 Mai 2011

Sur la finitude des (semi)-groupes d'automates

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr