Mean Quantitative Coverability in Stochastic Graph Transformation SystemsThe authors gratefully acknowledge support by the European Research Council (ERC) under grants 587327 ``DOPPLER'' and 320823 ``RULE''. Electronic Communications of the EASST Volume 68 (2014) Proceedings of the 8th International Workshop on Graph-Based Tools (GraBaTs 2014) Mean Quantitative Coverability in Stochastic Graph Transformation Systems Vincent Danos, Tobias Heindel, Ricardo Honorato-Zimmer, Sandro Stucki 2 pages Guest Editors: Matthias Tichy, Bernhard Westfechtel Managing Editors: Tiziana Margaria, Julia Padberg, Gabriele Taentzer ECEASST Home Page: http://www.easst.org/eceasst/ ISSN 1863-2122 http://www.easst.org/eceasst/ ECEASST Mean Quantitative Coverability in Stochastic Graph Transformation Systems∗ Vincent Danos1, Tobias Heindel1, Ricardo Honorato-Zimmer1, Sandro Stucki2 School of Informatics, University of Edinburgh, Edinburgh, United Kingdom1 Programming Methods Laboratory, EPFL, Lausanne, Switzerland2 Abstract: Many classical problems for Petri nets, in particular reachability and cov- erability, have obvious counterparts for graph transformation systems. Similarly, many problems for stochastic Petri nets, seen as a model for chemical reaction net- works, are special cases of corresponding problems in graph transformation. For example, the evolution of the counts of chemical species in a test tube over time is a typical phenomenon from chemistry, which can faithfully be modelled and analysed using stochastic Petri nets. The corresponding mean quantitative coverability prob- lem for stochastic graph transformation is simple to describe – yet hard to solve. This extended abstract summarises the fundamental ideas and challenges. Keywords: Stochastic Graph Transformation, Coverability, Rate Equation, Markov Processes, Mean-Field Theories Reachability and coverability are well-known problems for Petri nets and graph transformation systems [EN94, BDK+12]. For stochastic graph transformation systems (SGTS) [THRB10], both problems give rise to families of related quantitative questions about the continuous time Markov process that is specified by the SGTS. As a first example, we might want to know the probability that a certain graph can be reached at some point in time, starting from a given finite graph or, more generally, from a given initial distribution over all finite graphs. The simple question that is at the core of previous and ongoing work of the authors [DHHS14, FDK+09] concerns the mean quantitative coverability for SGTS: how many occurrences of a fixed graph motif, the observable graph pattern, can one expect to find at a given time in the future in a stochastically evolving graph (given by an SGTS); i.e., we want to track the mean occurrence count of the observable graph pattern as it evolves over time. This is quite similar to asking about the evolution of the concentration of a specific chemical species in a test tube over time, which, in Petri net terms, means that we have to compute the function that gives for each time in the future the expected number of tokens in a given place. Computing the latter function is hard, even for the case for stochastic Petri nets with finite state space because it typ- ically amounts to solving the master equation, which is a linear system of differential equations with one variable for each reachable marking. For stochastic (finite state) graph transformation system, it is even non-trivial to show that we can write down the proper system of differential equations [DHHS14]. Analytic solutions or numerical methods with guaranteed precision are typically not available or too expensive to compute. Thus, in practice, one uses suitable approximations that perform ∗ The authors gratefully acknowledge support by the European Research Council (ERC) under grants 587327 “DOPPLER” and 320823 “RULE”. 1 / 2 Volume 68 (2014) Mean Quantitative Coverability in SGTS well according to experience. For example, the rate equation of stochastic Petri nets is suitable for many (bio-)chemical applications. But even for some very simple graph transformation systems, such as the voter model [DGL+12], good approximations schemes are difficult to obtain [Gle13]. Mean-field approximations from physics and in particular statistical mechanics provide a host of inspiring examples. However, we are just beginning to pioneer this new area on the graph transformation map. Bibliography [BDK+12] N. Bertrand, G. Delzanno, B. König, A. Sangnier, J. Stückrath. On the Decidabil- ity Status of Reachability and Coverability in Graph Transformation Systems. In Ti- wari (ed.), 23rd International Conference on Rewriting Techniques and Applications (RTA’12) , RTA 2012, May 28 - June 2, 2012, Nagoya, Japan. LIPIcs 15, pp. 101– 116. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. doi:10.4230/LIPIcs.RTA.2012.101 http://dx.doi.org/10.4230/LIPIcs.RTA.2012.101 [DGL+12] R. Durrett, J. P. Gleeson, A. L. Lloyd, P. J. Mucha, F. Shi, D. Sivakoff, J. E. S. Socolar, C. Varghese. Graph fission in an evolving voter model. Proceedings of the National Academy of Sciences 109(10):3682–3687, 2012. doi:10.1073/pnas.1200709109 http://www.pnas.org/content/109/10/3682.abstract [DHHS14] V. Danos, T. Heindel, R. Honorato-Zimmer, S. Stucki. Approximations for Stochas- tic Graph Rewriting. In 16th International Conference on Formal Engineering Meth- ods, ICFEM 2014, Luxemburg, Nov 3–5. Lecture Notes in Computer Science. Springer, 2014. [EN94] J. Esparza, M. Nielsen. Decidability Issues for Petri Nets. Technical report RS-94-8, BRICS, May 1994. http://www.brics.dk/RS/94/8/ [FDK+09] J. Feret, V. Danos, J. Krivine, R. Harmer, W. Fontana. Internal coarse-graining of molecular systems. Proceedings of the National Academy of Sciences 106(16):6453– 6458, 2009. doi:10.1073/pnas.0809908106 http://www.pnas.org/content/106/16/6453.abstract [Gle13] J. P. Gleeson. Binary-State Dynamics on Complex Networks: Pair Approximation and Beyond. Physical Review X 3:021004, Apr 2013. doi:10.1103/PhysRevX.3.021004 http://link.aps.org/doi/10.1103/PhysRevX.3.021004 [THRB10] P. Torrini, R. Heckel, I. Ráth, G. Bergmann. Stochastic Graph Transformation with Regions. ECEASST 29, 2010. http://journal.ub.tu-berlin.de/index.php/eceasst/article/view/413 Proc. GraBaTs 2014 2 / 2 http://dx.doi.org/10.4230/LIPIcs.RTA.2012.101 http://dx.doi.org/10.4230/LIPIcs.RTA.2012.101 http://dx.doi.org/10.1073/pnas.1200709109 http://www.pnas.org/content/109/10/3682.abstract http://www.brics.dk/RS/94/8/ http://dx.doi.org/10.1073/pnas.0809908106 http://www.pnas.org/content/106/16/6453.abstract http://dx.doi.org/10.1103/PhysRevX.3.021004 http://link.aps.org/doi/10.1103/PhysRevX.3.021004 http://journal.ub.tu-berlin.de/index.php/eceasst/article/view/413