Groupe automatique
# 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).$
