Special Issue: Membrane ComputingNo Access

AN UNIVERSALITY RESULT FOR A (MEM)BRANE CALCULUS BASED ON MATE/DRIP OPERATIONS

Microsoft Research Cambridge, 7, J.J. Thomson Avenue, Cambridge, CB3 0FB, UK

and

Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucureşti, Romania

Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain

Search for more papers by this author

https://doi.org/10.1142/S0129054106003693Cited by:29 (Source: Crossref)

Abstract

Operations with membranes are essential both in brane calculi and in membrane computing. In this paper we take four basic operations from brane calculi, pino, exo, mate, drip, we express them in terms of the membrane computing formalism, and then we investigate the computing power of the P systems using the mate, drip operations as unique evolution rules. All operations are controlled by – and make evolve – multisets of protein-objects embedded in the membranes themselves (not contained in the compartments of the cell, as standard in membrane computing; all compartments delimited by membranes are here empty). Somewhat surprisingly, for systems which use the mate, drip operations we obtain the Turing completeness. The power of P systems based on other operations remains to be investigated.

Keywords:

AMSC: 68Q42, 68Q45, 68Q85

References

N. Busi and R. Gorrieri , On the computational power of brane calculi , Third Workshop on Computational Methods in Systems Biology ( 2005 ) . Google Scholar
L. Cardelli, Brane calculi – interactions of biological membranes, Lecture Notes in Computer Science 3082, Computational Methods in Systems Biology. International Conference, CMSB 2004 (2004) (Springer-Verlag, Berlin, 2005) pp. 257–280. Google Scholar
J. Dassow and Gh. Păun , Regulated Rewriting in Formal Language Theory ( Springer-Verlag , Berlin , 1989 ) . Crossref, Google Scholar
J. Dassow, Gh. Păun and A. Salomaa, Handbook of Formal Languages 2, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, Berlin, 1997) pp. 101–154. Crossref, Google Scholar
S. A. Greibach, Theoretical Computer Science 7, 311 (1978). Crossref, Google Scholar
M. Harrison , Introduction to Formal Language Theory ( Addison-Wesley , Reading, MA , 1978 ) . Google Scholar
Gh. Păun, Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143 (and Turku Center for Computer Science–TUCS Report 208, November 1998, www.tucs.fi) . Google Scholar
Gh. Păun , Membrane Computing. An Introduction ( Springer-Verlag , Berlin , 2002 ) . Crossref, Google Scholar
A. Salomaa , Formal Languages ( Academic Press , New York , 1973 ) . Google Scholar
The membrane computing web page: http://psystems.disco.nimib.it . Google Scholar