Partager cette page :

Réécriture et problème du mot.

le 16 février 2010

de 15h30 à 17h00

ENS Rennes Salle du conseil

Intervention d'Yves Lafont, professeur à Marseille et chercheur à l'Institut de Mathématiques de Luminy (séminaire du département Informatique et télécommunications).

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
Thématique(s)
Formation, Recherche - Valorisation
Contact
Claude Jard

Mise à jour le 1 mars 2010