10.23638/LMCS-16(3:2)2020
Behr, Nicolas
Nicolas
Behr
Sobocinski, Pawel
Pawel
Sobocinski
Rule Algebras for Adhesive Categories
episciences.org
2020
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
contact@episciences.org
episciences.org
2019-02-05T09:18:24+01:00
2021-01-14T16:11:41+01:00
2020-07-03
eng
Journal article
https://lmcs.episciences.org/5164
arXiv:1807.00785
1860-5974
PDF
1
Logical Methods in Computer Science ; Volume 16, Issue 3 ; 1860-5974
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.