Computing Critical Pairs in 2-Dimensional Rewriting Systems

Abstract : Rewriting systems on words are very useful in the study of monoids. In good cases, they give finite presentations of the monoids, allowing their manipulation by a computer. Even better, when the presentation is confluent and terminating, they provide one with a notion of canonical representative for the elements of the presented monoid. Polygraphs are a higher-dimensional generalization of this notion of presentation, from the setting of monoids to the much more general setting of n-categories. Here, we are interested in proving confluence for polygraphs presenting 2-categories, which can be seen as a generalization of term rewriting systems. For this purpose, we propose an adaptation of the usual algorithm for computing critical pairs. Interestingly, this framework is much richer than term rewriting systems and requires the elaboration of a new theoretical framework for representing critical pairs, based on contexts in compact 2-categories.
Type de document :
Communication dans un congrès
Christopher Lynch. Rewriting Theory and Applications, 2010, Edinburgh, United Kingdom. 6, pp.227-242, 2010, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://drops.dagstuhl.de/opus/volltexte/2010/2655〉. 〈10.4230/LIPIcs.RTA.2010.227〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00473983
Contributeur : Samuel Mimram <>
Soumis le : samedi 17 avril 2010 - 20:03:08
Dernière modification le : mercredi 14 février 2018 - 14:17:52
Document(s) archivé(s) le : mardi 28 septembre 2010 - 11:53:04

Fichiers

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

Identifiants

Collections

CEA | INSMI | DRT | LIST

Citation

Samuel Mimram. Computing Critical Pairs in 2-Dimensional Rewriting Systems. Christopher Lynch. Rewriting Theory and Applications, 2010, Edinburgh, United Kingdom. 6, pp.227-242, 2010, Leibniz International Proceedings in Informatics (LIPIcs). 〈http://drops.dagstuhl.de/opus/volltexte/2010/2655〉. 〈10.4230/LIPIcs.RTA.2010.227〉. 〈inria-00473983〉

Partager

Métriques

Consultations de la notice

131

Téléchargements de fichiers

216