Approximations for stochastic graph rewriting

Speaker : Vincent Danos
ENS
Date: 07/07/2015
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40

Abstract

We present a method to compute approximate descriptions of a class of stochastic systems. For the method to apply, the system must be presented as a Markov chain on a state space consisting in graphs or graph-like objects, and jumps must be described by transformations which follow a finite set of local rules. The method is a form of static analysis. The output is a system of coupled ordinary differential equations (ODE) which tracks the mean evolution of the number of (typically small) subgraphs. In some cases, these ODEs form an exact and finite description of these mean numbers. But even when the ODE description is only an approximation, it can often reveal interesting properties of the original system.