Universality results for P systems based on brane calculi operations

Operations with membranes are essential both in brane calculi as well as in membrane computing. In this paper, we attempt to express six basic operations of brane calculi, viz., pino, exo, phago, bud, mate, drip in terms of the membrane computing formalism. We also investigate the computing power of P systems controlled by phago/exo, pino/exo, bud/mate as well as the mate/drip operations. We give an improvement to a characterization of RE using mate/drip operations given in [L. Cardelli, Gh. Paun, An universality result based on mate/drip operations, International Journal of Foundations of Computer Science (in press)]. We also give a characterization of RE using a new operation, called selective mate. We conjecture that it is not possible to obtain Turing completeness using only one of the six operations. We also conjecture that the pairs of operations we have considered for completeness, in this paper, are complete: it is impossible to obtain Turing completeness with any other pair of operations. (c) 2006 Elsevier B.V. All rights reserved.