210228
20190317000228.0
0302-9743
ISI
000364827900001
doi
10.1007/978-3-319-20860-2_1
978-3-319-20859-6
CONF
Moment Semantics for Reversible Rule-Based Systems
2015
Switzerland
Springer International Publishing
2015
Conference Papers
Lecture Notes in Computer Science
9138
Invited paper. This work was sponsored by the European Research Council (ERC) under the grants DOPPLER (587327) and RULE (320823).
We develop a notion of stochastic rewriting over marked graphs – i.e. directed multigraphs with degree constraints. The approach is based on double-pushout (DPO) graph rewriting. Marked graphs are expressive enough to internalize the ‘no-dangling-edge’ condition inherent in DPO rewriting. Our main result is that the linear span of marked graph occurrence-counting functions – or motif functions – form an algebra which is closed under the infinitesimal generator of (the Markov chain associated with) any such rewriting system. This gives a general procedure to derive the moment semantics of any such rewriting system, as a countable (and recursively enumerable) system of differential equations indexed by motif functions. The differential system describes the time evolution of moments (of any order) of these motif functions under the rewriting system. We illustrate the semantics using the example of preferential attachment networks; a well-studied complex system, which meshes well with our notion of marked graph rewriting. We show how in this case our procedure obtains a finite description of all moments of degree counts for a fixed degree.
Stochastic Processes
Moment Semantics
Reversible Computing
Graph Rewriting
Rule-Based Systems
Danos, Vincent
Heindel, Tobias
Honorato-Zimmer, Ricardo
246677
Stucki, Sandro
152185
7th International Conference on Reversible Computation
Grenoble, France
July 16-17, 2015
Krivine, Jean
ed.
Stefani, Jean-Bernard
ed.
3-26
Reversible Computation 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings
453172
http://infoscience.epfl.ch/record/210228/files/momsem_1.pdf
Postprint
Postprint
252187
LAMP
U10409
oai:infoscience.tind.io:210228
conf
IC
GLOBAL_SET
152185
EPFL-CONF-210228
EPFL
NON-REVIEWED
PUBLISHED
CONF