A Homotopical Completion Procedure with Applications to Coherence of Monoids

Yves Guiraud 1, 2 Philippe Malbos 2, 3 Samuel Mimram 4
2 PI.R2 - Design, study and implementation of languages for proofs and programs
PPS - Preuves, Programmes et Systèmes, Inria Paris-Rocquencourt, UPD7 - Université Paris Diderot - Paris 7, CNRS - Centre National de la Recherche Scientifique : UMR7126
Abstract : One of the most used algorithm in rewriting theory is the Knuth-Bendix completion procedure which starts from a terminating rewriting system and iteratively adds rules to it, trying to produce an equivalent convergent rewriting system. It is in particular used to study presentations of monoids, since normal forms of the rewriting system provide canonical representatives of words modulo the congruence generated by the rules. Here, we are interested in extending this procedure in order to retrieve information about the low-dimensional homotopy properties of a monoid. We therefore consider the notion of coherent presentation, which is a generalization of rewriting systems that keeps track of the cells generated by confluence diagrams. We extend the Knuth-Bendix completion procedure to this setting, resulting in a homotopical completion procedure. It is based on a generalization of Tietze transformations, which are operations that can be iteratively applied to relate any two presentations of the same monoid. We also explain how these transformations can be used to remove useless generators, rules, or confluence diagrams in a coherent presentation, thus leading to a homotopical reduction procedure. Finally, we apply these techniques to the study of some examples coming from representation theory, to compute minimal coherent presentations for them: braid, plactic and Chinese monoids.
Type de document :
Communication dans un congrès
Van Raamsdonk, Femke. RTA - 24th International Conference on Rewriting Techniques and Applications - 2013, Jun 2013, Eindhoven, Netherlands. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 21, pp.223-238, 2013, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.RTA.2013.223〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00818253
Contributeur : Philippe Malbos <>
Soumis le : vendredi 26 avril 2013 - 19:17:39
Dernière modification le : jeudi 15 novembre 2018 - 20:27:28
Document(s) archivé(s) le : mardi 4 avril 2017 - 00:00:05

Fichier

rta13FinalLong.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Yves Guiraud, Philippe Malbos, Samuel Mimram. A Homotopical Completion Procedure with Applications to Coherence of Monoids. Van Raamsdonk, Femke. RTA - 24th International Conference on Rewriting Techniques and Applications - 2013, Jun 2013, Eindhoven, Netherlands. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 21, pp.223-238, 2013, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.RTA.2013.223〉. 〈hal-00818253〉

Partager

Métriques

Consultations de la notice

995

Téléchargements de fichiers

152