Elsevier

Biosystems

Volume 59, Issue 3, March 2001, Pages 139-158
Biosystems

From cells to computers: computing with membranes (P systems)

https://doi.org/10.1016/S0303-2647(00)00143-XGet rights and content

Abstract

The aim of this paper is to introduce to the reader the main ideas of computing with membranes, a recent branch of (theoretical) molecular computing. In short, in a cell-like system, multisets of objects evolve according to given rules in the compartments defined by a membrane structure and compute natural numbers as the result of halting sequences of transitions. The model is parallel, nondeterministic. Many variants have already been considered and many problems about them were investigated. We present here some of these variants, focusing on two central classes of results: (1) characterizations of the recursively enumerable sets of numbers and (2) possibilities to solve NP-complete problems in polynomial — even linear — time (of course, by making use of an exponential space). The results are given without proofs. An almost complete bibliography of the domain, at the middle of October 2000, is also provided.

Section snippets

The computing bio-cell

Assertions about the computing-like activities which take place in alive cells can be found in many places, the reactions by which chemical compounds, energy, and information are handled in the complex structure of a cell being often interpreted as computing processes (see e.g. Bray (1995) and references therein). The incentive to define P systems (initially, in Păun (1998), they were called supper-cell systems) was the question whether or not these statements are just metaphoras, or a formal

The cell membrane: structure and functions

The many (formal) notions which we will soon consider when defining our computing devices will not only be biology-like, but most of them will correspond in a direct way to notions from the biochemistry of the membranes of alive cells.

A cell has a complex structure, with several compartments delimited inside the main membrane by several inner membranes: the nucleus, the Golgi aparatus, several vesicles, etc. In principle, all these membranes are similar, they are separators and filters, so that

The computing math-cell

Let us now try to abstract from the structure and the functioning of an alive cell and informally describe the symbolic counterpart of the bio-cell. A partial formalization of the notions discussed below can be found in Section 5.

Everything takes place in a membrane structure, which is a hierarchical arrangement of membranes, all of them placed in a main membrane, called the skin membrane. This one delimits the system from its environment. The membranes should be understood as three-dimensional

Membrane computing and natural computing

The details from the biochemistry of (animal and vegetal, alike) membranes sketched in Section 2 only show that the ingredients we use in P systems, mainly in what concerns the way of communicating through membranes, are ‘realistic’, in the sense that they have a resemblance with actual biochemical facts. However, this means nothing in what concerns the possible implementations of the model.

Up to now, there was no attempt to carry out a computation, even for solving a toy problem, by using

A formal definition of a P system

In this section, we go closer to mathematics and introduce a formal counterpart of the computing cell as sketched in Section 3.

A membrane structure can be mathematically represented by a tree, in the natural way, or by a string of matching parentheses. The tree of the structure in Fig. 1 is given in the same figure, while the parenthetic representation of that structure is the following:[1[2]2[3]3[4[5]5[6[8]8[9]9]6[7]7]4]1.

The tree representation makes possible considering various parameters,

Examples

Before recalling some results about the computing power of P systems of the types introduced in the previous section or involving further ingredients, we shall consider three examples for the basic variant considered above, one for each type of tasks a P system can solve.

Example 1

(Generative task) Consider the P system of degree 4Π1=(V,T,C,μ,w1,w2,w3,w4,(R11),(R22),(R33),(R44),4),V={a,b,b′,c,e,f},T={e},C=0̷,μ=[1[2[3]3[4]4]2]1,w1=λ,R1=0̷,ρ1=0̷,w2=λ,R2={b′→b,b→bein4,r1:ff→f,r2:f→δ},ρ2={r1>r2},w3

Computational completeness

At the end of Section 3, we have mentioned that P systems as introduced above are equivalent with Turing machines. More precisely, we have the following theorem (the family of recursively enumerable sets of vectors of natural numbers is denoted3 by PsRE):

Theorem 1

NP2(Pri,

P systems with string objects

In P systems with symbol objects, as discussed in the previous sections, we use a rather noneconomical representation of numbers, the base one. Having in mind that many of the objects present in cells are complex molecules, even strings, such as the DNA molecules, it is natural to consider also P systems with the objects represented by strings. Then, the evolution rules should be string processing operations.

An important distinction here is whether or not we take into account the multiplicities

P systems with worm objects

In P systems with symbol objects, we work with multisets and the result of a computation is a natural number or a vector of natural numbers; in the case of P systems with string objects, we work with sets of strings and the result of a computation is a string. We can combine the two ideas: we can work with multisets of strings and consider as the result of a computation the number of strings present in the halting configuration in a given membrane or sent out of the system during the

Solving NP in P by P

Let us now pass to a fundamental question: are P systems computationally useful? From a theoretical point of view, the answer is affirmative: in the framework of P systems we can naturally create an exponential working space and this can be used for solving hard problems in a feasible time. Exponentially many objects can be produced in all types of P systems – see the very first example from Section 6. However, such a work space is not sufficient: an important theorem from Zandron et al. (2000d)

Further results, research topics

There are many results in P systems area, other than referring to characterizations of the power of Turing machines and to solving hard problems in a feasible (parallel) time. The bibliography which follows is meant to help the reader in having an image about the current state of the domain. We only mention here some of the main problems approached and results given in some of these papers: bridge theorems, relating the internal and the external modes of reading the result of a computation (

Further Suggested Reading

Atanasiu, 2000, Calude and Păun, 2000, Dassow and Păun, 2000, Freund and Freund, 2000, Freund, 2000, Frisco, 2000, Krishna et al., 2000, Manca, 2000, Martin-Vide and Mitrana, 2000, Martin-Vide and Păun, 2000b, Păun, 1999, Păun et al., 2000c, Păun and Yokomori, 2000, Zandron et al., 2000a, Zandron et al., 2000b, Zandron et al., 2000e, Rama, 2000, Krishna, 2000, Krishna and Rama, 2000e, Păun, 2000c, Păun, 2000d

Acknowledgements

Work partially supported by a grant of NATO Science committee, Spain 2000–2001.

References (68)

  • T. Head

    Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors

    Bullet. Mathemat. Biol.

    (1987)
  • L.M. Adleman

    Molecular computation of solutions to combinatorial problems

    Science

    (1994)
  • B. Alberts

    Essential Cell Biology. An Introduction to the Molecular Biology of the Cell

    (1998)
  • Atanasiu, A., 2000. Arithmetic with membranes. Pre-proc. Workshop on Multiset Processing, Curtea de Argeş, Romania, TR...
  • Atanasiu, A., Martin-Vide, C., 2000a. Recursive calculus with membranes. Submitted for...
  • Atanasiu, A., Martin-Vide, C., 2000b. P systems and context-free languages. Submitted for...
  • Baranda, A.V., Castellanos, J., Molina, R., Arroyo, F., Mingo, L.F., 2000. Data structures for implementing transition...
  • D. Bray

    Protein molecules as computational elements in living cells

    Nature

    (1995)
  • Calude, C., Păun, Gh., 2000. Computing with Cells and Atoms. Taylor and Francis, London (Chapter 3: Computing with...
  • Castellanos, J., Păun, Gh., Rodriguez-Paton, A., 2000. P systems with worm objects. IEEE Seventh Intern. Conf. on...
  • Ciobanu, G., Paraschiv, D., 2000. Membrane software. A P system simulator. Submitted for...
  • J. Dassow et al.

    Regulated Rewriting in Formal Language Theory

    (1989)
  • J. Dassow et al.

    On the power of membrane computing

    J. Univ. Comput. Sci.

    (1999)
  • Dassow, J., Păun, Gh., 2000. Concentration controlled P systems, submitted for...
  • Freund, R., 1999a. Generalized P systems. In: Ciobanu, G., Păun, Gh. (Eds.), Fundamentals of Computation Theory....
  • R. Freund

    Generalized P systems with splicing and cutting/recombination

    Grammars

    (1999)
  • Freund, R., 2000. Sequential P systems. Workshop on New Computing Paradigms, TU University, Vienna, pp....
  • Freund, R., Freund, F., 2000. Molecular computing with generalized homogeneous P systems. In: Condon, A., Rozenberg, G....
  • Freund, R., Păun, Gh., 2000. On the number of variables in graph-grammars, programmed, and matrix grammars. Submitted...
  • Freund, R., Martin-Vide, C., Păun, Gh., 2000. Computing with membranes: three more collapsing hierarchies. Submitted...
  • Frisco, P., 2000. Membrane computing based on splicing: improvements. Pre-proc. Workshop on Multiset Processing, Curtea...
  • Ito, M., Martin-Vide, C., Păun, Gh., 2000. A characterization of Parikh sets of ET0L languages in terms of P systems....
  • Krishna, S.N., 2000. Computing with simple P systems. Pre-proc. Workshop on Multiset Processing, Curtea de Argeş,...
  • S.N. Krishna et al.

    A variant of P systems with active membranes: solving NP-complete problems

    Rom. J. Info. Sci. Technol.

    (2000)
  • S.N. Krishna et al.

    On the power of P systems with sequential and parallel rewriting

    Int. J. Comput. Math.

    (2000)
  • Krishna, S.N., Rama, R., 2000c. Computability, complexity and languages of P systems. Submitted for...
  • Krishna, S.N., Rama, R., 2000d. On simple P systems with external output. Submitted for...
  • Krishna, S.N., Rama, R., 2000e. A note on partial/full parallel rewriting in P systems, Bulletin if the EATCS, in...
  • Krishna, S.N., Krithivasan, K., Rama, R., 2000. P systems with picture objects. Submitted for...
  • R.J. Lipton

    Using DNA to solve NP-complete problems

    Science

    (1995)
  • W.R. Loewenstein

    The Touchstone of Life. Molecular Information, Cell Communication, and the Foundations of Life

    (1999)
  • S.S. Mader

    Membrane structure and function

  • Maliţa, M., 2000. Membrane computing in Prolog. Pre-proc. Workshop on Multiset Processing, Curtea de Argeş, Romania, TR...
  • Manca, V., 2000. Monoidal systems and membrane systems. Pre-proc. Workshop on Multiset Processing, Curtea de Argeş,...
  • Cited by (52)

    • Verification of Spatial and Temporal Modalities in Biochemical Systems

      2015, Electronic Notes in Theoretical Computer Science
    • Converting differential-equation models of biological systems to membrane computing

      2013, BioSystems
      Citation Excerpt :

      structural (Muniyandi and Zin, 2010b) and distributed (Ciobanu et al., 2006) arrangements are captured, in which objects and processes evolve according to the rules local to their compartment; furthermore the compartmentalized biological processes lead to emergent behaviour (Teuscher, 2007) in the overall system; the stochastic nature of biological systems are expressed (Besozzi et al., 2008a; Spicher et al., 2008) by the non-deterministic (Baranda et al., 2001) and maximal parallel evolution (Păun, 2001) strategy of membrane systems. In an ODE model, a stochastic ODE (Gard, 1987) would be required (although the stochastic influence is incorporated by introducing parameters as stochastic processes or inserting stochastic processes to the driving system equations (Carletti et al., 2004), once again modularity of stochastic behaviour is not achieved).

    • Developmental modelling with SDS

      2010, Computers and Graphics (Pergamon)
      Citation Excerpt :

      Using an evolutionary algorithm, he was able to evolve a 2D cell pattern that resembled the French flag from a single zygote cell. Some developmental models incorporate hierarchies as an explicit feature, for example, P-systems [44], Vaario's Multi-Level Interaction Simulation (MLIS) language [16] and McCormack's Cellular Developmental Model (CDM) [45]. To date, the predominant applications for P-systems and MLIS have not been in the creative domain (P-systems have been used primarily for studying computation and MLIS was designed to evolve artificial neural networks).

    • Timed P Automata

      2009, Electronic Notes in Theoretical Computer Science
    View all citing articles on Scopus

    A preliminary version of this paper has been presented at the workshop on grammar systems, Bad Ischl, Austria, July 2000.

    View full text