Skip to Main content Skip to Navigation
Journal articles

Towards 3-Dimensional Rewriting Theory

Samuel Mimram 1, 2 
1 LMeASI - Laboratoire Modélisation et Analyse de Systèmes en Interaction
LIST (CEA) - Laboratoire d'Intégration des Systèmes et des Technologies : DRT/LIST
Abstract : String rewriting systems have proved very useful to study monoids. In good cases, they give finite presentations of monoids, allowing computations on those and their manipulation by a computer. Even better, when the presentation is confluent and terminating, they provide one with a notion of canonical representative of 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. One of the main purposes of this article is to give a progressive introduction to the notion of $\higher-dimensional\ rewriting\ system$provided by polygraphs, and describe its links with classical rewriting theory, string and term rewriting systems in particular. After introducing the general setting, we will be interested in proving local confluence for polygraphs presenting 2-categories and introduce a framework in which a finite 3-dimensional rewriting system admits a finite number of critical pairs
Complete list of metadata
Contributor : Bruno Savelli Connect in order to contact the contributor
Submitted on : Monday, June 25, 2018 - 4:17:53 PM
Last modification on : Saturday, June 25, 2022 - 9:11:32 PM

Links full text





Samuel Mimram. Towards 3-Dimensional Rewriting Theory. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2014, 10, pp.1-47. ⟨10.2168/LMCS-10(2:1)2014⟩. ⟨cea-01822999⟩



Record views