License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.227
URN: urn:nbn:de:0030-drops-26552
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2655/
Go to the corresponding LIPIcs Volume Portal

Mimram, Samuel

Computing Critical Pairs in 2-Dimensional Rewriting Systems

pdf-format:
10002.MimramSamuel.2655.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{mimram:LIPIcs:2010:2655,
  author =	{Samuel Mimram},
  title =	{{Computing Critical Pairs in 2-Dimensional Rewriting Systems}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{227--242},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2655},
  URN =		{urn:nbn:de:0030-drops-26552},
  doi =		{10.4230/LIPIcs.RTA.2010.227},
  annote =	{Keywords: Rewriting system, polygraph, presentation of a category, critical pair, unification, confluence, compact 2-category, context}
}

Keywords: Rewriting system, polygraph, presentation of a category, critical pair, unification, confluence, compact 2-category, context
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI