title: Groupe automatique
text: # Groupe automatique
  
  En mathématiques, un groupe automatique est un groupe décrit à l'aide d'automates finis. L'intérêt des groupes automatiques est que le problème du mot est décidable. C'est un cas particulier d'une structure automatique.
  
  ## Définition
  
  Soit G un groupe qui admet un ensemble fini A d'éléments générateurs. Le groupe G est automatique par rapport à A s'il existe un automate M sur l'alphabet A et des automates $M_x$ sur l'alphabet $A^2$ pour tout x dans A ∪{e} où e est l'élément neutre tels que :
  
  * le langage de l'automate M accepte au moins un représentant pour chaque élément du groupe. Plus précisément, pour tout élément g de G, l'automate reconnaît au moins un mot fini sur A qui représente l'élément g ;
  * L'automate $M_a$ accepte une paire $(w_1,$ $w_2)$ si et seulement si $w_1a$ = $w_2$ dans G et w1 et $w_2$ sont acceptés par M.
  
  ## Exemples
  
  Les groupes finis sont automatiques.
  
  ## Algorithme quadratique pour le problème du mot
  
  Étant donné un groupe G, le problème du mot consiste à déterminer algorithmiquement si deux mots $w_1,$ $w_2$ représentent le même élément dans le groupe. Étant donné un groupe automatique G, il existe un algorithme en temps quadratique (en les longueurs des deux mots à tester) qui résout le problème du mot. On peut montrer qu'il existe un algorithme qui prend en entrée un mot w sur A et qui calcule en temps $O(|w|^2)$ un mot de L(M) qui représente le même élément. Ainsi, l'algorithme pour résoudre le problème du mot fonctionne comme suit :
  
  * calculer $w_1'$ dans L(M) qui représente $w_1$ ;
  * calculer $w_2'$ dans L(M) qui représente $w_2$ ;
  * Tester si $(w_1',$ $w_2')$ est dans $L(M_e).$
  