License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2018.11
URN: urn:nbn:de:0030-drops-96781
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9678/
Go to the corresponding LIPIcs Volume Portal

Behr, Nicolas ; Sobocinski, Pawel

Rule Algebras for Adhesive Categories

pdf-format:
LIPIcs-CSL-2018-11.pdf (0.8 MB)

Abstract

We show that every adhesive category gives rise to an associative algebra of rewriting rules induced by the notion of double-pushout (DPO) rewriting and the associated notion of concurrent production. In contrast to the original formulation of rule algebras in terms of relations between (a concrete notion of) graphs, here we work in an abstract categorical setting. Doing this, we extend the classical concurrency theorem of DPO rewriting and show that the composition of DPO rules along abstract dependency relations is, in a natural sense, an associative operation. If in addition the adhesive category possesses a strict initial object, the resulting rule algebra is also unital. We demonstrate that in this setting the canonical representation of the rule algebras is obtainable, which opens the possibility of applying the concept to define and compute the evolution of statistical moments of observables in stochastic DPO rewriting systems.

BibTeX - Entry

@InProceedings{behr_et_al:LIPIcs:2018:9678,
  author =	{Nicolas Behr and Pawel Sobocinski},
  title =	{{Rule Algebras for Adhesive Categories}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9678},
  URN =		{urn:nbn:de:0030-drops-96781},
  doi =		{10.4230/LIPIcs.CSL.2018.11},
  annote =	{Keywords: Adhesive categories, rule algebras, Double Pushout (DPO) rewriting}
}

Keywords: Adhesive categories, rule algebras, Double Pushout (DPO) rewriting
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

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