Vincent Danos ; Russell Harmer ; Ricardo Honorato-Zimmer - Thermodynamic graph-rewriting

lmcs:1573 - Logical Methods in Computer Science, June 24, 2015, Volume 11, Issue 2 -
Thermodynamic graph-rewriting

Authors: Vincent Danos ; Russell Harmer ; Ricardo Honorato-Zimmer

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.

Volume: Volume 11, Issue 2
Published on: June 24, 2015
Submitted on: February 28, 2014
Keywords: Computer Science - Logic in Computer Science,Quantitative Biology - Molecular Networks


Consultation statistics

This page has been seen 478 times.
This article's PDF has been downloaded 389 times.