Invited Talk: Nicolas Behr

An Introduction to Stochastic Mechanics for Categorical Rewriting Systems

Many of the well-established traditional approaches to reason about stochastic rewriting systems are centred around the notion of traces (I.e. sequences of rewriting steps), not least since traces are the natural forms of output obtained from suitable simulation engines. On the other hand, taking the Kappa framework (Danos et al.) for modelling bio-chemical reaction systems as a prominent example, it is often the case that simulation-based techniques may be fruitfully augmented by certain static analysis techniques that aim to predict or extract invariants for rewriting systems, or to obtain ODE systems to describe statistical properties. Motivated by a marked absence of a principled implementation of the general mathematical framework of continuous-time Markov chains (CTMCs) within rewriting theory, we developed starting in 2015 the stochastic mechanics framework, based at its core on our novel concept of so-called rule algebras. This new approach serves three main purposes: to formulate stochastic rewriting systems in precisely the general mathematical CTMC formalism, to render accessible techniques from mathematical physics for the analysis of rewriting systems, and to provide a solid semantics and theoretical foundation for the aforementioned static analysis techniques. In this talk, I will give an introduction to the latest development version of this framework (formulated for rewriting over M-adhesive categories and for rules with application conditions) that is capable of faithfully implementing bio- and organo-chemical reactions, but also rewriting over many other datatypes such as in particular planar binary trees (PBTs). The aim of this presentation is to stimulate a discussion on the precise relationship of the algebraic (commutator-based) techniques suggested by the rule algebra formalism with the techniques known in the term graph rewriting community, focussing for concreteness on the example of PBT rewriting.


11th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2020)