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


Consultation statistics

This page has been seen 436 times.
This article's PDF has been downloaded 247 times.