Nicolas Behr ; Pawel Sobocinski - Rule Algebras for Adhesive Categories

lmcs:5164 - Logical Methods in Computer Science, July 3, 2020, Volume 16, Issue 3 -
Rule Algebras for Adhesive Categories

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
    Fundings :
      Source : OpenAIRE Graph
    • Rule-algebraic Simple Rewriting; Funder: European Commission; Code: 753750

    Linked data

    Source : ScholeXplorer IsPartOf DOI 10.4230/lipics.csl.2018
    • 10.4230/lipics.csl.2018
    LIPIcs, Volume 119, CSL'18, Complete Volume
    Ghica, Dan ; Jung, Achim ;

    1 Document citing this article

    Consultation statistics

    This page has been seen 733 times.
    This article's PDF has been downloaded 291 times.