Problème du mot et géométrie de la réécriture

option du Master  2 MDFI (2010-2011)

Yves Lafont (IML-LDP)



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