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 11 Mars 2014

Croissance des semi-groupes d’automate: le cas (étonnant) des automates à deux états

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

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