TY - GEN

T1 - Thermodynamic Graph-rewriting

AU - Danos, Vincent

AU - Harmer, Russ

AU - Honorato Zimmer, Ricardo

PY - 2013

Y1 - 2013

N2 - We develop a new ‘thermodynamic’ approach to stochastic graph-rewriting. The ingredients are a finite set of reversible graph-rewriting rules G (called generating rules), a finite set of connected graphs P (called energy patterns), and an energy cost function ϵ:P→R . The idea is that G defines the qualitative dynamics by showing which transformations are possible, while P and ε specify the long-term probability π of any graph reachable under G . Given G,P , we construct a finite set of rules G P which (i) has the same qualitative transition system as G , and (ii) when equipped with suitable rates, defines a continuous-time Markov chain of which π is the unique fixed point. The construction relies on the use of site graphs and a technique of ‘growth policy’ for quantitative rule refinement which is of independent interest. The ‘division of labour’ between the qualitative and the long-term quantitative aspects of the dynamics leads to intuitive and concise descriptions for realistic models (see the example in §4). It also guarantees thermodynamical consistency (aka detailed balance), otherwise known to be undecidable, which is important for some applications. Finally, it leads to parsimonious parameterizations of models, again an important point in some applications.

AB - We develop a new ‘thermodynamic’ approach to stochastic graph-rewriting. The ingredients are a finite set of reversible graph-rewriting rules G (called generating rules), a finite set of connected graphs P (called energy patterns), and an energy cost function ϵ:P→R . The idea is that G defines the qualitative dynamics by showing which transformations are possible, while P and ε specify the long-term probability π of any graph reachable under G . Given G,P , we construct a finite set of rules G P which (i) has the same qualitative transition system as G , and (ii) when equipped with suitable rates, defines a continuous-time Markov chain of which π is the unique fixed point. The construction relies on the use of site graphs and a technique of ‘growth policy’ for quantitative rule refinement which is of independent interest. The ‘division of labour’ between the qualitative and the long-term quantitative aspects of the dynamics leads to intuitive and concise descriptions for realistic models (see the example in §4). It also guarantees thermodynamical consistency (aka detailed balance), otherwise known to be undecidable, which is important for some applications. Finally, it leads to parsimonious parameterizations of models, again an important point in some applications.

U2 - 10.1007/978-3-642-40184-8_27

DO - 10.1007/978-3-642-40184-8_27

M3 - Conference contribution

SN - 978-3-642-40183-1

T3 - Lecture Notes in Computer Science

SP - 380

EP - 394

BT - CONCUR 2013 – Concurrency Theory

PB - Springer Berlin Heidelberg

CY - Berlin, Heidelberg

ER -