From individuals to populations: a mean field semantics for process algebra.

*(English)*Zbl 1209.68307Summary: A new semantics in terms of mean field equations is presented for WSCCS (Weighted Synchronous Calculus of Communicating Systems). The semantics captures the average behaviour of the system over time, but without computing the entire state space, therefore avoiding the state space explosion problem. This allows easy investigation of models with large numbers of components. The new semantics is shown to be equivalent to the standard Discrete Time Markov Chain semantics of WSCCS as the number of processes tends to infinity. The method of deriving the semantics is illustrated with examples drawn from biology and from computing.

##### MSC:

68Q55 | Semantics in the theory of computing |

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

92D25 | Population dynamics (general) |

PDF
BibTeX
XML
Cite

\textit{C. McCaig} et al., Theor. Comput. Sci. 412, No. 17, 1557--1580 (2011; Zbl 1209.68307)

Full Text:
DOI

##### References:

[1] | Anderson, R.M.; May, R.M., The population-dynamics of micro-parasites and their invertebrate hosts, Philosophical transactions of the royal society of London series B, 291, 451-524, (1981) |

[2] | Baeten, J.C.M., A brief history of process algebra, Theoretical computer science, 335, 2-3, 131-146, (2005) · Zbl 1080.68072 |

[3] | Begon, M.; Bennet, M.; Bowers, R.G.; French, N.P.; Hazel, S.M.; Turner, J., A clarification of transmission terms in host-microparasite models: numbers, densities and areas, Epidemiology and infection, 129, 147-153, (2002) |

[4] | Begon, M.; Townsend, C.R.; Harper, J.L., Ecology: from individuals to ecosystems, (2005), Wiley-Blackwell |

[5] | Benkirane, S.; Hillston, J; McCaig, C.; Norman, R.; Shankland, C., Improved continuous approximation of PEPA models through epidemiological examples, (), 59-74 · Zbl 1283.92064 |

[6] | Beverton, R.J.H.; Holt, S.J., () |

[7] | L. Brodo, P. Degano, C. Priami, A tool for quantitative analysis of calculus processes, in: ICALP Satellite Workshops, 2000, pp. 535-550. |

[8] | M. Calder, S. Gilmore, J. Hillston, Automatically deriving ODEs from process algebra models of signalling pathways, in: Proceedings of Computational Methods in Systems Biology, CMSB 2005, 2005, pp. 204-215. |

[9] | Cardelli, L., On process rate semantics, Theoretical computer science, 391, 190-215, (2008) · Zbl 1133.68054 |

[10] | Dunn, A.M.; Hatcher, M.J.; Terry, R.S.; Tofts, C., Evolutionary ecology of vertically transmitted parasites: transovarial transmission of a Microsporidian sex ratio distorer in gammarus duebeni, Parasitology, 111, S91-S109, (1995) |

[11] | Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics: A foundation for computer science, (1989), Addison-Wesley · Zbl 0668.00003 |

[12] | M.J. Hatcher, C. Tofts, The evolution of polygenic sex determination with potential for environmental manipulation, Technical Report UMCS-95-4-2, Department of Computer Science, University of Manchester, 1995. |

[13] | Hillston, J., Fluid flow approximation of PEPA models, (), 33-42 |

[14] | Coffman, E.G.; Kadota, T.T.; Shepp, L.A., On the asymptotic optimality of first-fit storage allocation, IEEE transactions on software engineering, 11, 235-239, (1985) |

[15] | Kermack, W.O.; McKendrick, A.G., Contributions to the mathematical theory of epidemics I, Proceedings of the royal society of London series A, 115, 700-721, (1927) · JFM 53.0517.01 |

[16] | Kuratowski, K., Topology: volume 1, (1966), Polish Scientific Publishers · Zbl 0158.40901 |

[17] | Kurtz, T.G., Solutions of ordinary differential equations as limits of pure jump Markov processes, Journal of applied probability, 7, 49-58, (1970) · Zbl 0191.47301 |

[18] | Levin, S.A.; Grenfell, B.; Hastings, A.; Perelson, A.S., Mathematical and computational challenges in population biology and ecosystems science, Science, 275, 334-343, (1997) · Zbl 1225.92058 |

[19] | C. McCaig, From individuals to populations: changing scale in process algebra models of biological systems, Ph.D. Thesis, University of Stirling, 2007. http://hdl.handle.net/1893/398. |

[20] | C. McCaig, M. Begon, R. Norman, C. Shankland, A rigorous approach to investigating common assumptions about disease transmission: process algebra as an emerging modelling methodology for epidemiology, in: Emerging Modelling Methodologies, Theory in Biosciences (2010) (special issue), in press (doi:10.1007/s12064-010-0106-8). |

[21] | C. McCaig, M. Begon, R. Norman, C. Shankland, A symbolic investigation of superspreaders, in: Algebraic Biology, Bulletin of Mathematical Biology (2010) (special issue) (in press). · Zbl 1214.92064 |

[22] | C. McCaig, R. Norman, C. Shankland, Deriving mean field equations from large process algebra models, Technical Report CSM-175, Department of Computing Science and Mathematics, University of Stirling, March 2008. http://hdl.handle.net/1893/1584. · Zbl 1171.92336 |

[23] | McCaig, C.; Norman, R.; Shankland, C., From individuals to populations: a symbolic process algebra approach to epidemiology, Mathematics in computer science, 2, 3, 139-155, (2009) |

[24] | Monroy, R, A process algebra model of the immune system, (), 526-533 |

[25] | Norman, R.; Shankland, C., Developing the use of process algebra in the derivation and analysis of mathematical models of infectious disease, (), 404-414 |

[26] | R. Pelánek, Fighting state space explosion: review and evaluation, in: Proc. of Formal Methods for Industrial Critical Systems, FMICS’08, vol. 5596, 2009, pp. 37-52. |

[27] | D. Sumpter, From bee to society: an agent based investigation of honeybee colonies, Ph.D. Thesis, UMIST, 2000. |

[28] | Sumpter, D.J.T.; Broomhead, D.S., Relating individual behaviour to population dynamics, Proceedings of the royal society of London series B, 268, 925-932, (2001) · Zbl 1323.92228 |

[29] | Tofts, C., Describing social insect behaviour using process algebra, Transactions of the society for computer simulation, 9, 227-283, (1992) |

[30] | Tofts, C., Processes with probabilities, priority and time, Formal aspects of computing, 6, 536-564, (1994) · Zbl 0820.68072 |

[31] | Tofts, C., Exact, analytic, and locally approximate solutions to discrete event-simulation problems, Simulation practice and theory, 6, 721-759, (1998) · Zbl 0924.68211 |

[32] | C. Tofts, Exploiting strong attractors to slaughter monsters — taming 10^1500 states and beyond, Technical Report HPL-2006-121, HP Laboratories, Bristol, 2006. |

[33] | Turner, J.; Begon, M.; Bowers, R.G., Modelling pathogen transmission: the interrelationship between local and global approaches, Proceedings of the royal society of London series B, 270, 105-112, (2002) |

[34] | West, R.W.; Thompson, J.R., Models for the simple epidemic, Mathematical biosciences, 141, 29-39, (1997) · Zbl 0881.92030 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.