000210228 001__ 210228
000210228 005__ 20180913063231.0
000210228 022__ $$a0302-9743
000210228 02470 $$2ISI$$a000364827900001
000210228 0247_ $$2doi$$a10.1007/978-3-319-20860-2_1
000210228 020__ $$a978-3-319-20859-6
000210228 037__ $$aCONF
000210228 245__ $$aMoment Semantics for Reversible Rule-Based Systems
000210228 269__ $$a2015
000210228 260__ $$aSwitzerland$$bSpringer International Publishing$$c2015
000210228 336__ $$aConference Papers
000210228 490__ $$aLecture Notes in Computer Science$$v9138
000210228 500__ $$aInvited paper. This work was sponsored by the European Research Council (ERC) under the grants DOPPLER (587327) and RULE (320823).
000210228 520__ $$aWe 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.
000210228 6531_ $$aStochastic Processes
000210228 6531_ $$aMoment Semantics
000210228 6531_ $$aReversible Computing
000210228 6531_ $$aGraph Rewriting
000210228 6531_ $$aRule-Based Systems
000210228 700__ $$aDanos, Vincent
000210228 700__ $$aHeindel, Tobias
000210228 700__ $$aHonorato-Zimmer, Ricardo
000210228 700__ $$0246677$$aStucki, Sandro$$g152185
000210228 7112_ $$a7th International Conference on Reversible Computation$$cGrenoble, France$$dJuly 16-17, 2015
000210228 720_1 $$aKrivine, Jean$$eed.
000210228 720_1 $$aStefani, Jean-Bernard$$eed.
000210228 773__ $$q3-26$$tReversible Computation 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015, Proceedings
000210228 8564_ $$s453172$$uhttps://infoscience.epfl.ch/record/210228/files/momsem_1.pdf$$yPostprint$$zPostprint
000210228 909C0 $$0252187$$pLAMP$$xU10409
000210228 909CO $$ooai:infoscience.tind.io:210228$$pconf$$pIC
000210228 917Z8 $$x152185
000210228 937__ $$aEPFL-CONF-210228
000210228 973__ $$aEPFL$$rNON-REVIEWED$$sPUBLISHED
000210228 980__ $$aCONF