Samuel Mimram - Towards 3-Dimensional Rewriting Theory

lmcs:750 - Logical Methods in Computer Science, April 4, 2014, Volume 10, Issue 2 - https://doi.org/10.2168/LMCS-10(2:1)2014
Towards 3-Dimensional Rewriting Theory

Authors: Samuel Mimram ORCID-iD

    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.


    Volume: Volume 10, Issue 2
    Published on: April 4, 2014
    Accepted on: June 25, 2015
    Submitted on: October 29, 2010
    Keywords: Computer Science - Logic in Computer Science
    Fundings :
      Source : OpenAIRE Research Graph
    • Categories, Homotopy and Rewriting; Funder: French National Research Agency (ANR); Code: ANR-13-BS02-0005

    Linked data

    Source : ScholeXplorer IsReferencedBy ARXIV 1505.07161
    Source : ScholeXplorer IsReferencedBy DOI 10.4204/eptcs.183.1
    Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1505.07161
    • 10.4204/eptcs.183.1
    • 10.4204/eptcs.183.1
    • 10.4204/eptcs.183.1
    • 10.48550/arxiv.1505.07161
    • 1505.07161
    Presenting Finite Posets
    Mimram, Samuel ;

    7 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 424 times.
    This article's PDF has been downloaded 448 times.