L.M.P.A
Laboratoire de Mathématiques Pures et Appliquées
Joseph Liouville

Evenement du jeudi 5 avril

  • Groupe de travail d’Algèbre du 5 avril

    Pierre Gillibert ()

    Le problème de l’ordre dans les groupes d’automates

    Un automate de Mealy M (ou encore un transducteur lettre à lettre) est un automate fini muni de fonctions de production. En fixant un état comme état initial l’automate induit un endomorphisme de l’arbre des mots. Le semi-groupe engendré par M est le semi-groupe engendré par tous ces endomorphismes. Si les fonctions de production sont bijectives alors les endomorphismes induits sont des automorphismes. On considère alors le groupe d’automate engendré par ces automorphismes.

    Alesin, en utilisant un groupe d’automate, donna une construction simple d’un groupe infini, finiment engendré et dont tout élément est d’ordre fini, aussi appelé groupe de Burnside. Grigorchuk a trouvé un groupe d’automate qui est de Burnside, moyennable, non élémentairement moyennable et de croissance intermédiaire. Ce qui résout le problème de Milnor et le problème de Day.

    Le problème du mot et résoluble dans tout groupe d’automate (réduction de Eilenberg). Par contre Sunic et Ventura (2012) on construit un groupe d’automate dont le problème conjugaison est indécidable.

    A partir d’une machine de Turing on peut construire un groupe d’automate qui simule la machine de Turing. Plus précisément pour toute configuration de la machine de Turing, on peut construire explicitement un élément du groupe tel que la machine de s’arrête si et seulement l’élément est d’ordre fini. En particulier si la machine de Turing est universelle, le problème de finitude de l’ordre d’un élément est indécidable.

    Informations : 13:30 - 13:30
Vous pouvez recevoir les évenements de l'agenda directement dans votre logiciel de gestion d'agenda à l'aide de l'adresse : http://lmpa.univ-littoral.fr/exports/lmpa_agenda.ics

Agenda