Problème du mot et géométrie de la réécriture
Cours fondamental conseillé : logique et théorie du calcul
Le problème suivant est indécidable : peut-on
déduire une égalité u = 1 (dans un groupe)
à partir d'une liste donnée d'égalités
(problème du mot) ? Nous allons expliquer la
démonstration de ce résultat classique en utilisant des
méthodes modernes, à base de réécriture de
mots. Ce travail va nous conduire aux développements les plus
récents d'une nouvelle branche de l'algèbre et de
l'informatique théorique : la théorie homotopique du
calcul.
Programme :
• groupes libres et réécriture
• problème du mot et machines affines
• extensions de Higman-Neuman-Neuman
• théorème de Novikov-Boone
• homologie de la réécriture
Bibliographie :
• Y. Lafont, Réécriture et problème du mot, Gazette des mathématiciens 120, avril 2009
• Y. Lafont, Algèbre et géométrie de la réécriture, Ecole Jeunes Chercheurs en Informatique Mathématique, CIRM Marseille, 31 mars - 4 avril 2008
• Y. Lafont, Algebra and geometry of rewriting, Applied Categorical Structures 15 (4), août 2007