Nicolas Behr ; Pawel Sobocinski - Rule Algebras for Adhesive Categories

lmcs:5164 - Logical Methods in Computer Science, July 3, 2020, Volume 16, Issue 3 - https://doi.org/10.23638/LMCS-16(3:2)2020
Rule Algebras for Adhesive CategoriesArticle

Authors: Nicolas Behr ; Pawel Sobocinski

    We demonstrate that the most well-known approach to rewriting graphical structures, the Double-Pushout (DPO) approach, possesses a notion of sequential compositions of rules along an overlap that is associative in a natural sense. Notably, our results hold in the general setting of $\mathcal{M}$-adhesive categories. This observation complements the classical Concurrency Theorem of DPO rewriting. We then proceed to define rule algebras in both settings, where the most general categories permissible are the finitary (or finitary restrictions of) $\mathcal{M}$-adhesive categories with $\mathcal{M}$-effective unions. If in addition a given such category possess an $\mathcal{M}$-initial object, the resulting rule algebra is unital (in addition to being associative). We demonstrate that in this setting a 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.


    Volume: Volume 16, Issue 3
    Published on: July 3, 2020
    Accepted on: June 8, 2020
    Submitted on: February 5, 2019
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,Mathematics - Combinatorics,Mathematics - Category Theory,16B50, 60J27, 68Q42 (Primary) 60J28, 16B50, 05E99 (Secondary),F.4.2,G.3,G.2.2
    Funding:
      Source : OpenAIRE Graph
    • Rule-algebraic Simple Rewriting; Funder: European Commission; Code: 753750

    1 Document citing this article

    Consultation statistics

    This page has been seen 1776 times.
    This article's PDF has been downloaded 433 times.