Moment Semantics for Reversible Rule-Based Systems

Vincent Danos, Tobias Heindel, Ricardo Honorato-zimmer, Sandro Stucki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationReversible Computation
Subtitle of host publication7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings
PublisherSpringer International Publishing
Pages3-26
Number of pages24
ISBN (Electronic)978-3-319-20860-2
ISBN (Print)978-3-319-20859-6
DOIs
Publication statusPublished - 20 Jun 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume9138
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Moment Semantics for Reversible Rule-Based Systems'. Together they form a unique fingerprint.

Cite this