Séminaire des Doctorants et Doctorantes

La réécriture algébrique

by Benjamin Dupont

Europe/Paris
Fokko du Cloux (ICJ)

Fokko du Cloux

ICJ

Description
La réécriture est une théorie des relations d'équivalences utilisée en informatique fondamentale pour transformer des objets syntaxiques (termes, programmes, preuves, etc.) en utilisant des règles données, et en calcul formel fournissant une théorie du calcul. Depuis quelques années, des méthodes inspirées de cette théorie se sont développées dans diverses structures algébriques comme les monoïdes, les catégories de dimension supérieure ou les algèbres afin d'étudier ces structures. Dans cet exposé, nous présenterons les bases de la théorie de la réécriture, puis nous verrons comment les propriétés de terminaison et de confluence pour des systèmes de réécriture de mots permettent de décider du problème du mot dans un monoïde ou encore de fournir des critères de finitude homologique. Nous finirons par élargir les perspectives sur les nouvelles questions intervenant en réécriture, notamment pour les groupes et les catégories linéaires de dimension supérieure.