##  [Résolution du Problème des Mots](/fr/node/62348) 

 Définition

Processus de décision consistant à déterminer si deux mots en les générateurs d'une structure algébrique présentée représentent le même élément dans le quotient défini par les relations ; équivalemment, décider si un mot donné représente l'identité.

 

 

 

 

 

 





## Principe

Principe

Réduire les mots en utilisant les relations définissantes jusqu'à une forme canonique ou normale lorsque cela est possible, ou appliquer des procédures de décision (systèmes de réécriture, Knuth–Bendix, Todd–Coxeter, algorithmes spécifiques) qui aboutissent soit à l'égalité soit à la non-équivalence ; la décidabilité dépend de la classe des présentations.

 

 

 

 

 





## Démonstration

Démonstration

Dans un groupe libre engendré par a et b, le problème des mots se résout en annulant les paires inverses adjacentes : pour décider si aba^{-1}b^{-1} est l'identité, annuler systématiquement aa^{-1} et bb^{-1} jusqu'à épuisement des annulations, concluant à l'identité si le mot vide est obtenu.

 

 

 

 

## Mauvaise application

Mauvaise application

Confondre l'égalité syntaxique (séquences de symboles littéralement identiques) avec l'égalité dans le groupe sans effectuer de réduction par les relations, ou supposer la décidabilité pour des groupes finiment présentés quelconques — de nombreuses présentations conduisent à un problème des mots indécidable en général.

 

 

 

 

 





## Conséquence

Conséquence

Une procédure de décision correcte fournit soit un algorithme pour calculer des formes normales et résoudre ainsi des requêtes d'égalité, soit établit l'indécidabilité dans la classe ; les problèmes des mots résolus permettent des calculs effectifs dans le quotient, comme des vérifications d'appartenance et des tests d'homomorphisme.

 

 

 

 

## Inversion

Inversion

Contraster avec le problème de conjugaison (décider si deux éléments sont conjugués) ou le problème d'isomorphisme (décider l'isomorphisme de structures présentées) ; inverser la question échange l'égalité au sens des relations contre l'équivalence sous une autre relation.

 

 

 

 

 





## Limite

Limite

Portée limitée par la classe de structures algébriques et de présentations : les groupes libres, les groupes finis et de nombreuses classes spéciales ont des problèmes des mots décidables ; les groupes finiment présentés arbitraires peuvent présenter des problèmes des mots indécidables ; ressources de calcul et terminaison sont des limites pratiques.

 

 

 

 

 





## Tension sémantique

Tension sémantique

Problème des mots versus identité en langages formels ou égalité syntaxique : le problème des mots est sémantique (égalité dans le quotient défini par des relations), alors que l'identité syntaxique ignore les relations ; il rivalise aussi avec les problèmes de conjugaison et d'appartenance en tant que tâche décisionnelle centrale en algèbre.

 

 

 

 

 





## Synthèse

Synthèse

La résolution du problème des mots ramène la question d'égalité sous les relations définissantes à des réductions algorithmiques en formes normales ou à l'application de procédures de décision ; c'est le test algorithmique fondamental d'égalité dans les systèmes algébriques présentés, dont la solvabilité dépend de la classe algébrique et de la méthode de calcul choisie.