Problème du mot

Le problème du mot est un problème de décision en algèbre abstraite. Il consiste, pour une présentation donnée d'une structure algébrique, à répondre algorithmiquement (à décider) à la question suivante : étant donné une paire de termes ${\displaystyle t_{1}}$ et ${\displaystyle t_{2}}$ de la structure, est-ce que l'égalité ${\displaystyle t_{1}=t_{2}}$ est satisfaite ? Le premier problème de mot dont on a démontré l'indécidabilité fut le problème du mot dans les groupes. La démonstration a été annoncée par Tarski en 1949^[1] et publiée dans le livre Undecidable Theories^[2].

Le problème du mot en logique combinatoire est indécidable. Le problème du mot pour les groupes est indécidable en général, mais décidable dans de nombreux cas : il existe un algorithme qui décide si ${\displaystyle t_{1}=t_{2}}$ est vraie dans tous les groupes^[3]. Le problème du mot dans les groupes est aussi décidable pour de nombreuses classes de présentations de groupes, par exemple pour les groupes de Coxeter et plus généralement pour les groupes automatiques, mais est indécidable en général, pour une présentation quelconque d'un groupe par générateurs et relations. En 1955, Novikov a même prouvé qu'il existe des présentations de groupes ayant un problème du mot indécidable.

De nombreux problèmes de décision en mathématiques peuvent être formulés comme des problèmes du mot (voir la liste de problèmes indécidables).

Références

1. Solomon Feferman et Anita Burdman Feferman, Alfred Tarski, Life and Logic, Cambridge : Cambridge University Press, 2004 (ISBN 0-521-80240-7), p. 193.
2. (en) Alfred Tarski in collaboration with A. Mostowski and R. M. Robinson Undecidable theories. North Holland, 1953
3. D. Knuth, P. Bendix (1970). J. Leech, ed. Simple Word Problems in Universal Algebras. Pergamon Press. pp. 263–297

Articles connexes

• Combinatoire des mots
• Complétion de Knuth-Bendix
• Théorème de Muller-Schupp

• Portail de la logique
• Portail des mathématiques
• Portail de l'informatique théorique