Homotopy and homology of rewriting
Yves Lafont (Université d’Aix-Marseille)
This lecture presents deep connexions between various areas of maths and theoretical computing:
- word rewriting: convergent presentations of a monoid (or a category) ;
- homological algebra: homology groups of a monoid (or a category) ;
- braid groups and generalisations: Garside families in a monoid (or a category) ;
- higher categories and homotopical algebra: finite derivation type and polygraphic resolutions.
Outline of the lecture
This approach was initiated by Craig Squier (1987): by showing that the critical pairs of rewriting define generators for homology in dimension 3, he could build a finitely presentable monoid for which the word problem is decidable, but which has no convergent finite presentation. The result has been generalized to higher dimension by Yuji Kobayashi (1990), and then reformulated in a homotopical framework by Craig Squier himself (1994). It was adapted to the case of gaussian groups by Patrick Dehornoy and Yves Lafont (2003), which allows, for instance, to compute the homology of braid groups. Word rewriting was also generalized to the case of 2-presentations by Albert Burroni (1993) and Yves Lafont (2003). Following this, François Métayer introduced the notion of polygraphic resolution (2003), which is the homotopical version of free resolutions (2009). This is also called a cofibrant replacement in homotopical algebra.
A very partial and preliminary list of publications related to the content of this lecture:
- Craig Squier. Word problems and a homological finiteness condition for monoids. Journal of Pure and Applied Algebra, 49:201–217, 1987.
- Yuji Kobayashi. Complete rewriting systems and homology of monoid algebras. Journal of Pure and Applied Algebra, 65(3):263–275, 1990.
- Albert Burroni. Higher-dimensional word problems with applications to equational logic. Theoretical Computer Science, 115:43–62, 1993.
- Craig Squier, Friedrich Otto, & Yuji Kobayashi. A finiteness condition for rewriting systems. Theoretical Computer Science, 131:271–294, 1994.
- Patrick Dehornoy & Yves Lafont. Homology of gaussian groups. Annales de l’Institut Fourier, 53(2):489–540, 2003.
- Yves Lafont. Towards an algebraic theory of boolean circuits. Journal of Pure and Applied Algebra, 184:257–310, 2003.
- François Métayer. Resolutions by polygraphs. Theory and Applications of Categories, 11(7):148–184, 2003.
- Yves Lafont. Algebra and geometry of rewriting. Applied Categorical Structures, 15(4):415–437, 2007.
- Yves Lafont & François Métayer. Polygraphic resolutions and homology of monoids. Journal of Pure and Applied Algebra, 213:947–968, 2009.
- Patrick Dehornoy, François Digne, Eddy Godelle, Daan Krammer, & Jean Michel. Foundations of Garside Theory. EMS Tracts in Mathematics, 22, 2015.