Rewriting Theory for the Life Sciences: A Unifying Theory of CTMC Semantics


The Kappa biochemistry and the MØD organo-chemistry frameworks are amongst the most intensely developed applications of rewriting theoretical methods in the life sciences to date. A typical feature of these types of rewriting theories is the necessity to implement certain structural constraints on the objects to be rewritten (a protein is empirically found to have a certain signature of sites, a carbon atom can form at most four bonds, …). In this paper, we contribute to the theoretical foundations of these types of rewriting theory a number of conceptual and technical developments that permit to implement a universal theory of continuous-time Markov chains (CTMCs) for stochastic rewriting systems. Our core mathematical concepts are a novel rule algebra construction for the relevant setting of rewriting rules with conditions, both in Double- and in Sesqui-Pushout semantics, augmented by a suitable stochastic mechanics formalism extension that permits to derive dynamical evolution equations for pattern-counting statistics.

Graph Transformation, 13th International Conference, ICGT 2020, Proceedings, volume 12150 of Theoretical Computer Science and General Issues, Springer International Publishing
An encoding of Kappa rules for biochemical reaction systems in terms of rewriting theory rules (left), an example biochemical reaction system in Kappa syntax (middle) and an example of observables expressed as Kappa rules (right).