10.23638/LMCS-16(3:3)2020
https://lmcs.episciences.org/5426
Behr, Nicolas
Nicolas
Behr
Danos, Vincent
Vincent
Danos
Garnier, Ilias
Ilias
Garnier
European Commission
753750
Rule-algebraic Simple Rewriting
Combinatorial Conversion and Moment Bisimulation for Stochastic Rewriting Systems
We develop a novel method to analyze the dynamics of stochastic rewriting
systems evolving over finitary adhesive, extensive categories. Our formalism is
based on the so-called rule algebra framework and exhibits an intimate
relationship between the combinatorics of the rewriting rules (as encoded in
the rule algebra) and the dynamics which these rules generate on observables
(as encoded in the stochastic mechanics formalism). We introduce the concept of
combinatorial conversion, whereby under certain technical conditions the
evolution equation for (the exponential generating function of) the statistical
moments of observables can be expressed as the action of certain differential
operators on formal power series. This permits us to formulate the novel
concept of moment-bisimulation, whereby two dynamical systems are compared in
terms of their evolution of sets of observables that are in bijection. In
particular, we exhibit non-trivial examples of graphical rewriting systems that
are moment-bisimilar to certain discrete rewriting systems (such as branching
processes or the larger class of stochastic chemical reaction systems). Our
results point towards applications of a vast number of existing
well-established exact and approximate analysis techniques developed for
chemical reaction systems to the far richer class of general stochastic
rewriting systems.
episciences.org
Computer Science - Logic in Computer Science
Computer Science - Discrete Mathematics
Mathematical Physics
16B50, 60J27, 68Q42 (Primary) 60J28, 16B50, 05E99 (Secondary)
F.4.2
G.3
G.2.2
Attribution 4.0 International (CC BY 4.0)
2020-06-30
2020-07-10
2020-07-10
eng
journal article
arXiv:1904.07313
10.48550/arXiv.1904.07313
1860-5974
10.48550/arxiv.1904.07313
https://lmcs.episciences.org/5426/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 16, Issue 3
Researchers
Students