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.

Source : oai:arXiv.org:1807.00785

Volume: Volume 16, Issue 3

Published on: July 3, 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

This page has been seen 59 times.

This article's PDF has been downloaded 31 times.