Sesqui-Pushout Rewriting: Concurrency, Associativity and Rule Algebra Framework

Abstract

Sesqui-pushout (SqPO) rewriting is a variant of transformations of graph-like and other types of structures that fit into the framework of adhesive categories where deletion in unknown context may be implemented. We provide the first account of a concurrency theorem for this important type of rewriting, and we demonstrate the additional mathematical property of a form of associativity for these theories. Associativity may then be exploited to construct so-called rule algebras (of SqPO type), based upon which in particular a universal framework of continuous-time Markov chains for stochastic SqPO rewriting systems may be realized.

arXiv commentIn Proceedings GCM 2019, arXiv:1912.08966

References in corpus (1)

• Boson Normal Ordering via Substitutions and Sheffer-type Polynomials

Cited by in corpus (6)

• On Stochastic Rewriting and Combinatorics via Rule-Algebraic Methods
• Tracelets and Tracelet Analysis Of Compositional Rewriting Systems
• Reversibility and Composition of Rewriting in Hierarchies
• Efficient Computation of Graph Overlaps for Rule Composition: Theory and Z3 Prototyping
• Stochastic Graph Transformation For Social Network Modeling
• A Generalized Concurrent Rule Construction for Double-Pushout Rewriting