Characterizing the computational power of energy-based P systems

Abstract

We investigate the computational power of energy-based P systems, a model of membrane systems, where a fixed amount of energy is associated with each object and the rules transform single objects by adding or removing energy from them. We answer the recently proposed open questions about the power of such systems without priorities associated with the rules, for both sequential and maximally parallel modes. We also conjecture that deterministic energy-based P systems are not computationally complete.

Keywords:

• membrane computing
• distributed multiset rewriting
• P systems model with energy associated with compartments
• controlled distributed monadic rewriting
• theory of computing
• formal language theory

2010 AMS Subject Classifications::

• 03D25
• 68Q05
• 68Q10
• 68Q17
• 68Q45

ACM Computing Classification System Codes::

• F.1.1
• F.4.2
• F.4.3

Acknowledgements

The ideas exposed in this paper emerged during and after the Tenth Brainstorming Week on Membrane Computing (BWMC 10), held in Seville in conjunction with the International Conference on Developments in Membrane Computing, from 30 January to 3 February 2012. The first author gratefully acknowledges the project RetroNet by the Lombardy Region of Italy under the ASTIL Program (regional decree 6119, 20100618). The work of the other two authors was partially supported by Università degli Studi di Milano-Bicocca, Fondo di Ateneo per la Ricerca (FAR) 2011.