Membrane computing is a non-conventional computing paradigm devoted to getting inspiration from the architecture and functioning of living cells in order to devise new ways of computing. Cell features as in a hierarchically-arranged set of membranes are 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. Similar to living cells, these membranes (delimiting regions with reactors) 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 aspect in computing with P systems is communication complexity. Unfortunately, this aspect remains as one of the issues posed as a challenge for membrane computing. In hopes of addressing this issue, a previous work look into analysis of communication on a specific P system variant called Evolution-Communication P systems with energy (ECPe systems). The concept of ‘energy’ is introduced as a form of payment during communication. Dynamical communication measures were also presented to define communication-based complexity classes. Following this initial direction, this research will further the study of ECPe systems and the communication aspects of this model. We shall investigate the characterization of established communication-based complexity classes discussed in previous literatures, i.e. explore the communication resources needed by ECPe systems functioning as generators and deciders. We shall also look into characterizing the communication-based complexity classes of models related to ECPe systems, specifically, Evolution-Communication (EC) P systems and a restricted ECPe variant called Proton Pumping P systems.
References:
H. Adorna, Gh. Paun, M. Perez-Jimenez : On Communication Complexity in Evolution-Communication P systems, Romanian Journal of Information Science and Technology, 13, 2, 113--130, 2010.
A. Alhazov, M. Cavaliere: Proton Pumping P systems, Lecture Notes in Computer Science, 2933, 1--18, 2004.
A. Alhazov, R. Freund, A. Leporati, M. Oswald, C. Zandron: (Tissue) P systems with unit rules and energy assigned to membranes, Fundamenta Informaticae, 74, 4, 391--408, 2006.
A. Alhazov: Communication in Membrane Systems with Symbol Objects (Dissertation), Universitat Rovira I Virgili, 2006.
A. Alhazov, C. Ciubotaru, S. Ivanov, Y. Rogozhin: The Family of Languages Generated by Non-cooperative Membrane Systems, Lecture Notes in Computer Science, 6501, 65--80, 2011.
Z. Bangalan, K. Soriano, R. Juayong, F. Cabarle, H. Adorna, M.A. Martinez-del-Amor: A GPU Simulation for Evolution-Communication P Systems with Energy Having no Antiport Rules, Proceedings of the 11th Brainstorming Week on Membrane Computing, Seville, Spain, February 2013.
R. Barbuti, A. Maggiolo-Schettin, P. Milazzo, S. Tini: Compositional Semantics and Behavioral Equivalences for P Systems, Theoretical Computer Science, 395, 1, 77--100, 2008.
F.G. Cabarle, H. Adorna, M.A. Martinez-del-Amor, M.J. Perez-Jimenez: Improving GPU Simulations of Spiking Neural P Systems, Romanian Journal of Information Science and Technology, 15, 1, 5--20, 2012.
M. Cavaliere: Evolution-communication P systems, Lecture Notes in Computer Science, 2597, 134--145, 2003.
G. Ciobanu, Gh. Paun, Gh. Stefanescu: Sevilla Carpets associated with P systems. Proceedings of the Brainstorming Week on Membrane Computing (M. Cavaliere, C. Martin-Vide, Gh. Paun, eds.), Tarragona, Spain, 2003, Report RGML 26/03, 135--140.
E. Csuhaj-Varju, M. Margenstern, G. Vaszil, S. Verlan: On small universal antiport P systems, Theoretical Computer Science, 372, 2-3, 152--164, 2007.
D. Diaz-Pernil, P. Gallego-Ortiz, M. Gutierrez-Naranjo, M. Perez-Jimenez, A. Riscos-Nunez: Cell-like versus tissue-like P systems by means of Sevilla Carpets, Proceedings of the 7th Brainstorming Week on Membrane Computing, Sevilla, Spain, February 2009.
B. Donor, R. Juayong, H. Adorna: On the Communication Complexity of Sorting in Evolution-Communication P systems with Energy, Proceedings of the 12th Philippine Computing Science Congress, Laguna, Philippines, March 2012.
P. Frisco: The conformon-P system: a molecular and cell biology-inspired computability model, Theoretical Computer Science, 312, 2-3, 295--319, 2004.
M.A. Gutierrez-Naranjo, M.J. Perez-Jimenez: Searching Previous Configurations in Membrane Computing, Lecture Notes in Computer Science, 5957, 301--315, 2010.
N. Hernandez, R. Juayong, F. Cabarle, H. Adorna: A Simulation of Transition P Systems in Weighted Spiking Neural P Systems. Proceedings of Workshop on Computation: Theory and Practice 2013, Manila, Philippines, September 2013.
N. Hernandez, R. Juayong, H. Adorna: On Communication Complexity of Some Hard Problems in ECPe systems, Lecture Notes on Computer Science, 8340, 206--224, 2014.
R. Juayong, H. Adorna: A Note on the Universality of EC P Systems with Energy, Proceedings of the 2nd International Conference on Information Technology Convergence and Services (ITCS), Cebu, Philippines, August 2010.
R. Juayong, H. Adorna: Communication Complexity of Evolution-Communication P systems with Energy and Sevilla Carpet, Philippine Computing Journal, 6, 1, 34--40, 2010.
R. Juayong, H. Adorna: Computing on Evolution-Communication P systems with Energy Using Symport Only, Proceedings in Information and Communications Technology, 5, 145--159, 2012.
R. Juayong, H. Adorna: A Matrix Representation for Computations on Evolution-Communication P systems with Energy. Proceedings of the 11th Philippine Computing Science Congress 2011, Naga, Philippines, March 2011.
R. Juayong, F. Cabarle, H. Adorna: On the Simulations of Evolution-Communication P systems with Energy without Antiport Rules for GPUs, Proceedings of the 10th Brainstorming Week on Membrane Computing, Sevilla, Spain, April 2012.
R. Juayong, H. Adorna: Relating Computations in Non-cooperative Transition P systems and Evolution-Communication P systems with Energy, Fundamenta Informaticae, 136, 3, 209--217, 2015.
R. Juayong, H. Adorna: Relating the Languages of Transition P systems and Evolution-Communication P systems with Energy (Extended Abstract), Communications in Computer and Information Science, 472, 211--215, 2014.
M.A. Martinez-del-Amor: Accelerating Membrane Systems Simulators using High Performance Computing with GPU (Dissertation), University of Seville, 2013.
G. Mauri, A. Leporati, C. Zandron: Energy-Based Models of P systems, Lecture Notes in Computer Science, 5957, 104--124, 2010.
R. Milner: Communicating and Mobile Systems: the Pi-Calculus, Cambridge University Press, 1999.
A. Paun, Gh. Paun: The power of communication: P systems with symport/antiport, New Generation Computing, 20, 3, 295--305, 2002.
Gh. Paun: Computing with membranes, Journal of Computer and System Sciences, 61, 1, 108--143, 2000.
Gh. Paun: P systems with Active Membranes: Attacking NP-Complete Problems, Journal of Automata, Languages and Combinatorics, 6, 1, 75--90, 2001.
Gh. Paun: Membrane Computing - An Introduction, Springer-Verlag Berlin Heidelberg, 2002.
Gh. Paun: Further Open Problems in Membrane Computing, Proceedings of the Second Brainstorming Week on Membrane Computing, Sevilla, February 2004.
Gh. Paun: Introduction to Membrane Computing, In Applications of Membrane Computing (G. Ciobanu, M.J. Perez-Jimenez, Gh. Paun, eds.), Springer, 1--42, 2006.
Gh. Paun, M.J. 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.
Gh. Paun, M. J. Perez-Jimenez: Infinite hierarchy of Languages defined in dP systems, Theoretical Computer Science, 431, 4--12, 2012.
M.J. Perez-Jimenez: A Computational Complexity Theory In Membrane Computing, Lecture Notes in Computer Science, 5957, 125--148, 2010.
A.E. Porreca, A. Leporati, G. Mauri, C. Zandron: Introducing a Space Complexity Measure for P Systems, International Journal of Computers, Communications and Control, 4, 3, 301--310, 2009.
A. E. Porreca, G. Mauri, C. Zandron: Non-confluence in divisionless P systems with active membranes, Theoretical Computer Science, 411, 6, 878--887, 2010.
Turing, A.M.: On Computable Numbers with an Application to the Entscheidungs problem, Proceedings of the London Mathematical Society, Series 2, 42, 230--265, 1937.
A.C.Yao: Some complexity questions related to distributed computing, ACM Symposium on Theory of Computing, 209--213, 1979.
X. Zeng, H. Adorna, M. A. Martinez-del-Amor, L. Pan, M. Perez-Jimenez: Matrix Representation of Spiking Neural P Systems, Lecture Notes in Computer Science, 6501, 377--391, 2011.
The P systems Website: www.ppage.psystems.eu.