Réécriture et problème du mot.

Supposons que ab = 1 = bc dans un monoïde (non commutatif).
Peut-on en déduire que ba = 1 ? Même question si on suppose seulement que ab = 1.
Plus généralement, peut-on déduire une identité u = v à partir d'une liste d'axiomes 
u1 = v1 , . . . , un = vn ?
C'est ce qu'on appelle le problème du mot (pour les monoïdes).

La réécriture permet de résoudre ce problème, mais pas dans tous les cas, car celui-ci est indécidable.

La réécriture est aussi un bel outil pour aborder la théorie du calcul.

Bibliographie : Y. Lafont, Réécriture et problème du mot, Gazette des mathématiciens 120, avril 2009, SMF