Membrane Computing
From Scholarpedia
| Gheorghe Paun (2010), Scholarpedia, 5(1):9259. | doi:10.4249/scholarpedia.9259 | revision #72842 [link to/cite this article] | |||||||||||||||||||
Curator: Prof. Gheorghe Paun, Romanian Academy, Bucharest, Romania,, and Sevilla University, Spain
Contents |
Introduction
Membrane computing is a branch of natural computing which abstracts computing models from the architecture and the functioning of living cells, as well as from the organization of cells in tissues, organs (brain included) or other higher order structures such as colonies of cells (e.g., of bacteria).
Membrane computing was initiated in 1998 [1] and the literature of this area has grown very fast (already in 2003, Thompson Institute for Scientific Information, ISI, has qualified the initial paper as "fast breaking" and the domain as "emergent research front in computer science" - see http://esi-topics.com). A comprehensive presentation at the level of year 2002 can be found in [2] and a recent coverage of the domain can be found in [3]. Details and many downloadable papers can be found at the area website from http://ppage.psystems.eu.
The initial goal of membrane computing was to learn from cell biology something possibly useful to computer science, and the area quickly developed in this direction. Several classes of computing models - called P systems - were defined in this context, inspired from biological facts or motivated from mathematical or computer science points of view. Then, a number of applications were reported in several areas -- biology, bio-medicine, linguistics, computer graphics, economics, approximate optimization, cryptography, etc. Several software products for simulating P systems and attempts of implementing P systems on a dedicated hardware were reported.
The present text is only a quick introduction to membrane computing, only mentioning some basic ideas, types of results and of applications, and indicating some references and links.
A Quick Description of Membrane Computing
The main ingredients of a P system are (i) the membrane structure, delimiting compartments where (ii) multisets of objects evolve according to (iii) (reaction) rules of a bio-chemical inspiration. A membrane can contain other membranes, and the rules can process both objects and membranes. Thus, membrane computing can be defined as a framework for devising cell-like or tissue-like computing models which process multisets in compartments defined by means of membranes. These models are (in general) distributed and parallel. When a P system is considered as a computing device, hence it is investigated in terms of (theoretical) computer science, the main issues studied concern the computing power (in comparison with standard models from computability theory, especially Turing machines/Chomsky grammars and their restrictions) and the computing efficiency (the possibility of using parallelism for solving computationally hard problems in a feasible time). Computationally and mathematically motivated ways of using the rules and of defining the result of a computation are considered in this case. For instance, the main way of evolving a P system is based on a non-deterministic maximally parallel use of rules, with the system being synchronized (the clock is universal and in each time unit one uses a maximal multiset of rules in each membrane). Many variants are possible which are not mentioned here. When a P system is constructed as a model of a bio-chemical process, it is examined in terms of dynamical systems, with the (deterministic or probabilistic) evolution in time being the issue of interest, rather than a specific output.
Three main types of P systems have been considered until now: (i) cell-like P systems, (ii) tissue-like P systems, and (iii) neural-like P systems.
The first type imitates the (eukaryotic) cell, and its basic ingredient is the membrane structure, which is a
hierarchical arrangement of membranes (understood as three dimensional vesicles), delimiting compartments where
multisets of objects are placed; the objects are in general described by symbols from a given alphabet; rules for evolving these objects are
provided, also localized, acting in specified compartments or on specified membranes. The most common types of rules
are multiset rewriting rules (similar to chemical reactions, i.e., of the type 
, where 
and 
are
multisets of objects) and transport rules, e.g., symport or antiport rules [4], inspired by biological processes
(symport rules are of the form 
or 
, moving objects of multiset through a membrane, and antiport
rules are of the form 
, moving the objects of multiset outside a membrane at the same time with
moving the objects of multiset inside). Also the objects produced by a transition rule can pass through membranes
(we say that they are "communicated" among compartments), going from the current compartment to the external one (out) or to one of the internal ones (in), if any. The
rules can have several other forms, and their use can be controlled in various ways: promoters, inhibitors,
priorities, etc. Also the hierarchy of membranes can evolve, e.g., by creating and destroying membranes,
by division, by bio-like operations of exocytosis, endocytosis, phagocytosis, like in [5], and so on. Moreover, the objects can be of various types,
not only described by letters from a given alphabet, as in the basic class of P systems. For instance, the objects can be
described by strings, and then they evolve by string processing rules (for instance, rewriting, splicing, insertion-deletion),
they can be pairs name-value, called conformons [6], or even more complex data structures (arrays).
In tissue-like P systems [7], several one-membrane cells are considered as evolving in a common environment. They contain multisets of objects, while also the environment contains objects. Certain cells can communicate directly (channels are provided between them) and all cells can communicate through the environment. The channels can be given in advance or they can be dynamically established - this latter case appears in so-called population P systems [8]. In the case when the cells are simple, of a limited capacity (as the number of objects they contain or of rules they can use), we obtain the notion of P colony.
Finally, there are two types of neural-like P systems. One is similar to tissue-like P systems: the cells (neurons) are placed in the nodes of an arbitrary graph and they contain multisets of objects, but they also have a state which controls the evolution. Another variant was introduced in [9], under the name of spiking neural P systems (in short, SN P systems), where one uses only one type of objects, the spike, and the main information one works with is the distance between consecutive spikes.
All these types of P systems can be used in the generative mode (starting from the initial configuration, one proceeds until reaching a halting configuration, when a result is provided - in general, as the number of objects in a given output membrane), or in the accepting mode (for instance, a number is introduced in a membrane, in the form of the multiplicity of a given object, and this number is accepted if the computation halts) - the latter case leads to the notion of a P automaton. Extensions to vectors of numbers and to strings and languages were also investigated.
Power and Efficiency
From a theoretical point of view, P systems are both powerful (most classes of P systems are Turing complete, even when using ingredients of a reduced complexity - a small number of membranes, rules of simple forms, ways of controlling the use of rules directly inspired from biology are sufficient for generating/accepting all sets of numbers or languages generated by Turing machines; also small universal P systems of various types were produced) and efficient (many classes of P systems, especially those with enhanced parallelism, can solve computationally hard problems - typically NP-complete problems, but also harder problems, e.g., PSPACE-complete problems - in a feasible time - typically polynomial). Such a speed-up is obtained by trading space for time, with the space grown exponentially in a linear time by means of bio-inspired operations. The most investigated way to obtain such an exponential workspace is membrane division [10], but also membrane creation, membrane separation, string replication and other operations were used. These operations were then extended to cells in tissue-like P systems and even to neurons in SN P systems - and in all cases similar results were obtained: polynomial time solutions to computationally hard problems. Details can be found, e.g., in [11].
Applications
As a modeling framework, membrane systems is rather adequate for handling discrete (biological) processes, having many attractive features: easy understandability, scalability and programmability, inherent compartmentalization and ability to handle discrete data, etc. Most applications use cell-like P systems and tissue-like P systems, and the general protocol is the following: a P system is written which models a given process (biological - but not only: also economic processes, evolution of ecosystems, and of other processes were addressed in this framework), capturing the objects, compartments, and evolution rules; then a program is written to simulate this P system, or a program available on internet is used; after that, computer simulations are performed, tuning parameters until a correct description of the real process is obtained; related processes are then investigated within this framework. Details can be found in [12], including case studies and a description of existing software products (at the level of 2005).
There are also applications of other types, e.g., in computer graphics, cryptography, approximate optimization, and so on.
Comprehensive and up-dated information (at the level of year 2009) about all issues mentioned above, from the mathematical theory of P systems, power and efficiency included, for various different classes of P systems, to applications, available software and implementations, can be found in [3] (chapters are dedicated to each significant issue) and, providing the state-of-the-art, in the membrane computing website from http://ppage.psystems.eu. In particular, Chapter 1 of [3] (by Gh. Păun and G. Rozenberg) is a friendly and comprehensive introduction to membrane computing.
REFERENCES
1. 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}).
2. Gh. Păun: Membrane Computing. An Introduction. Springer, Berlin, 2002.
3. Gh. Păun, G. Rozenberg, A. Salomaa, eds.: Handbook of Membrane Computing. Oxford University Press, 2009.
4. A. Păun, Gh. Păun: The power of communication: P systems with symport/antiport. New Generation Computing, 20 (2002), 295--306.
5. L. Cardelli: Brane calculus. In Computational Methods in Systems Biology. International Conference CMSB 2004, Paris, France, May 2004, Revised Selected Papers, LNCS 3082, Springer, Berlin, 2005, 257--280.
6. P. Frisco: Computing with Cells. Advances in Membrane Computing. Oxford University Press, 2009.
7. C. Martin-Vide, Gh. Păun, J. Pazos, A. Rodriguez-Paton: Tissue P systems. Theoretical Computer Science, 296, 2 (2003), 295--326.
8. F. Bernardini, M. Gheorghe: Population P systems. Journal of Universal Computer Science, 10, 5 (2004), 509--539.
9. M. Ionescu, Gh. Păun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279--308.
10. Gh. Păun: P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics, 6, 1 (2001), 75--90.
11. M.J. Perez-Jimenez: A computational complexity theory in membrane computing. In Pre-proceedings of WMC10, Curtea de Arges, Romania, August 2009, 82--105.
12. G. Ciobanu, Gh. Păun, M.J. Perez-Jimenez, eds.: Applications of Membrane Computing. Springer, Berlin, 2006.
Internal references
- Valentino Braitenberg (2007) Brain. Scholarpedia, 2(11):2918.
- Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623.
- James Meiss (2007) Dynamical systems. Scholarpedia, 2(2):1629.
- Rodolfo Llinas (2008) Neuron. Scholarpedia, 3(8):1490.
- Arkady Pikovsky and Michael Rosenblum (2007) Synchronization. Scholarpedia, 2(12):1459.
- Paul M.B. Vitanyi (2009) Turing machine. Scholarpedia, 4(3):6240.
| Gheorghe Paun (2010) Membrane Computing. Scholarpedia, 5(1):9259, (go to the first approved version) Created: 9 March 2009, reviewed: 10 January 2010, accepted: 11 January 2010 |
