Membrane computing is a non-conventional computing paradigm devoted to getting inspiration from architecture and functioning of living cells in order to devise new ways of computing. Cell feature as in a hierarchically arranged set of membranes is incorporated in a computing model called a P system; each region bounded by a membrane may contain a multiset of objects that follows a set of rules for evolution and communication across membranes. As in living cells, these membranes act as processors that compute simultaneously while at the same time cooperating with each other, computing as a single unit. Thus, P systems are parallel and distributed computing devices. Being parallel and distributed devices, an important resource in P systems computation is communication. In this talk, we shall discuss how communication is analyzed in P systems. We first tackle static measures for analyzing communication. We also discuss relatively new dynamic measures used for analyzing communication in a P system model that uses some form of `energy' as communication cost. We show how these measures are used for defining communication-based complexity classes for problems, family of set of numbers and family of vector of numbers. We also discuss how these measures are extended for other P system models.
References:
1. H. Adorna, Gh. Paun, M. Perez-Jimenez: On Communication Complexity in Evolution- Communication P systems, Romanian Journal of Information Science and Technology, Vol. 13 No. 2 pp. 113-130, 2010.
2. A. Alhazov: Communication in Membrane Systems with Symbol Objects, Universitat Rovira I Virgili, Tarragona, Spain, 2006.
3. M. Cavaliere: Evolution-communication P systems. Membrane Computing. Proc. WMC 2002, Curtea de Arges ̧ (Gh. Paun et al., eds.), LNCS 2597, Springer, Berlin, 134-145, 2003.
4. E. Csuhaj-Varju, M. Margenstern, G. Vaszil, S. Verlan: On small universal antiport P systems. Theoretical Computer Science, 372, 152-164, 2007.
5. R. Juayong: Computing in Evolution-Communication P systems with Energy, University of the Philippines, Diliman, Thesis, 2012.
6. Gh. Paun, M. Perez-Jimenez: Solving Problems in a Distributed Way in Membrane Computing: dP systems. International Journal of Computers, Communication and Control 5, 2, 238-250, 2010.
7. Gh. Paun: Computing with membranes. Journal of Computer and System Sciences, 61, 1, 108–143, (2000), (and Turku Center for Computer Science-TUCS Report 208, November 1998, www.tucs.fi).
8. Gh. Paun: Introduction to Membrane Computing. In: Gabriel Ciobanu, Mario J. Perez- Jimenez and Gheorghe Paun, eds: Applications of Membrane Computing, Natural Computing Series. Springer, pp.1-42, 2006.
9. A.C.Yao: Some complexity questions related to distributed computing. ACM Symposium on Theory of Computing, 209-213, 1979.