Published in Volume XXI, Issue 2, 2011, pages 227-247

Authors: A. Spicher, S. Verlan


In this article we consider a new derivation mode for generalized communicating P systems (GCPS) corresponding to the functioning of population protocols (PP) and based on the sequential derivation mode and a fairness condition that permits to ensure a particular sequence of configurations. We show that PP can be seen as a particular variant of GCPS.We also consider several stochastic evolutions satisfying different fairness conditions and particularly focus on those corresponding to the run of a Gillespie’s SSA. This permits to further describe the dynamics of GCPS by a system of ODEs when the population size goes to the infinity.

Full Text (PDF)


[1] D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 235-253, 2006.

[2] D. Angluin, J. Aspnes, and D. Eisenstat. Stably computable predicates are semilinear. In PODC’06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, 292-299, New York, NY, USA, 2006. ACM Press.

[3] J. Aspnes and E. Ruppert. An introduction to population protocols. Bulletin of the Europ. Assoc. for Theor. Comp. Sci., 93:98-117, Oct. 2007.

4] C. Baier, M. Kwiatkowska. On the verification of qualitative properties of probabilistic processes under fairness constraints, Information Processing Letters, 66, 71-79, 1998.

[5] F. Bernardini, M. Gheorghe, M. Margenstern, and S. Verlan. How to synchronize the activity of all components of a P system? International Journal of Foundations of Computer Science., 19(5):1183-1198, 2008.

[6] O. Bournez, P. Chassaing, J. Cohen, L. Gerin, and X. Koegler. On the convergence of population protocols when population goes to infinity. Applied Mathematics and Computation, 215(4):1340-1350, 2009.

[7] J. Clement, C. Delporte-Gallet, H. Fauconnier, M. Sighireanu. Guidelines for the Verification of Population Protocols Proceedings of 31st International Conference on Distributed Computing Systems (ICDCS 2011), 215-224.

[8] G. Ciobanu, L. Pan, G. Paun, and M. J. P´erez-Jim´enez. P systems with minimal parallelism. Theor. Comput. Sci., 378(1):117-130, 2007.

[9] E. Csuhaj-Varj´u, G. Vaszil, and S. Verlan. On generalized communicating P systems with one symbol. In M. Gheorghe, T. Hinze, and G. Paun, editors, Proceedings of the Eleventh International Conference on Membrane Computing, 137-154. Verlag ProBusiness Berlin, 2010.

[10] E. Csuhaj-Varj´u and S. Verlan. On generalized communicating P systems with minimal interaction rules. Theor. Comp. Sci., 412(1-2):124-135, 2011.

[11] L. Edelstein-Keshet. Mathematical Models in Biology. Random House, New York, 1988.

[12] R. Freund and S. Verlan. A formal framework for static (tissue) P systems. In G. Eleftherakis, P. Kefalas, G. P˘aun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, 8th International Workshop, WMC 2007, Thessaloniki, Greece, June 25-28, 2007 Revised Selected and Invited Papers, volume 4860 of LNCS, 271-284. Springer, 2007.

[13] P. Frisco. Computing with Cells. Oxford University Press, 2009.

[14] D. T. Gillespie. Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem., 81(25):2340-2361, 1977.

[15] T.G. Kurtz. The Relationships between Stochastic and Deterministic Models for Chemical Reactions. Journal of Chemical Physics, 57(7):2976-2978, 1971.

[16] O. Michel, A. Spicher, and J.-L. Giavitto. Rule-based programming for integrative biological modeling – application to the modeling of the lambda phage genetic switch. Natural Computing, 8(4):865-889, december 2009.

[17] M. Presburger. Uber die vollstandig-keit eines gewissen systems der arithmetik ganzer zahlen, in welchemdie addition als einzige operation hervortritt. Comptes rendus du I Congres des Mathematicians des Pays Slaves, pages 92-101, 1929.

[18] G. Paun. Membrane Computing. An Introduction. Springer-Verlag, 2002.

[19] G. Paun, G. Rozenberg, and A. Salomaa. The Oxford Handbook Of Membrane Computing. Oxford University Press, 2009.

[20] W. Reisig. Petri Nets. An Introduction. Springer, 1985.

[21] G. Rozenberg and A. Salomaa. Handbook of Formal Languages, 3 volumes. Springer, 1997.

[22] A. Spicher, O. Michel, M. Cieslak, J.-L. Giavitto, and P. Prusinkiewicz. Stochastic p systems and the simulation of biochemical processes with dynamic compartments. BioSystems, 91(3):458-472, March 2008.

[23] A. Spicher, O. Michel, and J.-L. Giavitto. Understanding the dynamics of biological systems, chapter Interaction-based simulations for Integrative Spatial Systems Biology, 195-231. Springer, 2011.

[24] A. Spicher, S. Verlan. Generalized Communicating P Systems Working in Fair Sequential Mode. In G. Ciobanu, editor, 5th Workshop on Membrane Computing and Biologically Inspired Process Calculi, 83-94, also arXiv:1108.3432v1 [cs.DC], 2011.

[25] S. Verlan, F. Bernardini, M. Gheorghe, and M. Margenstern. Generalized communicating P systems. Theor. Comp. Sci., 404(1-2):170-184, 2008


  title={Generalized Communicating P Systems Working in Fair Sequential Mode},
  author={A. Spicher and S. Verlan},
  journal={Scientific Annals of Computer Science},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  publisher={``A.I. Cuza'' University Press}