HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00473983
Contributor : Samuel Mimram Connect in order to contact the contributor
Submitted on : Saturday, April 17, 2010 - 8:03:08 PM
Last modification on : Thursday, February 17, 2022 - 10:08:03 AM
Long-term archiving on: : Tuesday, September 28, 2010 - 11:53:04 AM

Files

mimram_rta10.pdf
Files produced by the author(s)

Identifiers

Collections

CEA | INSMI | DRT | LIST | ANR

Citation

Samuel Mimram. Computing Critical Pairs in 2-Dimensional Rewriting Systems. Rewriting Theory and Applications, 2010, Edinburgh, United Kingdom. pp.227-242, ⟨10.4230/LIPIcs.RTA.2010.227⟩. ⟨inria-00473983⟩

Share

Metrics

Record views

65

Files downloads

170