Thermodynamic Graph-Rewriting

DOI10.1007/978-3-642-40184-8_27MaRDI QIDQ2842121zbMATH OpenOpenAlexFDO

Authors Vincent Danos, Russ Harmer, Ricardo Honorato-Zimmer

Publication date 12 August 2013

Published in CONCUR 2013 – Concurrency Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.06022

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We develop a new thermodynamic approach to stochastic graph-rewriting. The ingredients are a finite set of reversible graph-rewriting rules called generating rules, a finite set of connected graphs P called energy patterns and an energy cost function. The idea is that the generators define the qualitative dynamics, by showing which transformations are possible, while the energy patterns and cost function specify the long-term probability $pi$ of any reachable graph. Given the generators and energy patterns, we construct a finite set of rules which (i) has the same qualitative transition system as the generators; and (ii) when equipped with suitable rates, defines a continuous-time Markov chain of which $pi$ 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. This division of labour between the qualitative and long-term quantitative aspects of the dynamics leads to intuitive and concise descriptions for realistic models (see the examples in S4 and S5). 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.

Recommendations

• Thermodynamic graph-rewriting
• Stochastic mechanics of graph rewriting
• Graphs and thermodynamics
• The entropy of a thermodynamic graph
• Transition graphs of reversible reaction systems
• Thermodynamic semirings
• Graph reconstruction and quantum statistical mechanics
• On graph rewritings
• scientific article; zbMATH DE number 3878382

Cited in

(10)

• Graphs and thermodynamics
• Rewriting theory for the life sciences: a unifying theory of CTMC semantics
• Rate equations for graphs
• Coarse-graining the dynamics of ideal branched polymers
• Moment semantics for reversible rule-based systems
• Thermodynamic graph-rewriting
• Incremental update for graph rewriting
• Stochastic mechanics of graph rewriting
• A knowledge representation meta-model for rule-based modelling of signalling networks
• Rewriting theory for the life sciences: a unifying theory of CTMC semantics

This page was built for publication: Thermodynamic Graph-Rewriting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842121)