Talk:Membrane Computing
The review article is rather clear and complete. I just suggest some improvements, mainly to made more clear the hierarchical structure of P systems – See below
1. 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]
DELETE (with the seminal paper published in 2000) ENDDEL
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].
MODIFIED Details and many downloadable papers, can be found at the area website from http://ppage.psystems.eu. ENDMOD
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.
2. 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.
SUBSTITUTE The rules can process both objects and membranes. WITH A membrane can contain, hierarchically, other membranes, and the rules can process both objects and membranes. ENDSUBST
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 oriented ways of using the rules and of defining the result of a computation are considered in this case.
COMMENT “Computationally and mathematically oriented ways” is not so clear. May be it’s better to say simply “Some different ways of using the rules and of defining the result of a computation have been considered, with implications on the computational power of P systems.” ENDCOMMENT
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.
SUBSTITUTE At this moment, there are three main types of P systems: (i) cell-like P systems, (ii) tissue-like P systems, and (iii) neural-like P systems. WITH Three main types of P systems have been considered till now: (i) cell-like P systems, (ii) tissue-like P systems, and (iii) neural-like P systems ENDSUBST
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),
DEL i.e., ENDDEL
delimiting compartments where multisets of objects
ADD and possibly inner membranes ENDADD
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 u\to v, where u and v are multisets of objects) and transport rules, e.g., symport or antiport rules [4], inspired by biological processes (symport rules are of the form (u,in) or (u,out), moving objects of multiset u through a membrane, and antiport rules are of the form (u,out;v,in), moving the objects of multiset u outside a membrane at the same time with moving the objects of multiset v inside). Also the objects produced by a transition rule can pass through membranes (we say that they are "communicated" among compartments)
ADD going from the current compartment to the external one (“out”) or to one of the internal ones (“in”), if any. ENDADD
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, 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
ADD “output” ENDADD
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.
3. 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
MODIFIED in tissue-like P systems and even to neurons in SN P systems – ENDMOD
and in all cases similar results were obtained: polynomial time solutions to computationally hard problems. Details can be found, e.g., in [11].
4. Applications
As a modeling framework,
MODIFIED membrane systems are ENDMOD
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
MODIFIED process (biological - but not only: also economic processes, evolution of ecosystems, and 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 processi s obtained; related processes are then investigated within this framework. ENDMOD
Details can be found in [12], including case studies and a description of existing software products (at the level of 2005).
There also are 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 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
MODIFIED [3] ENDMOD
(by Gh. Păun and G. Rozenberg) is a friendly and comprehensive introduction to membrane computing.
Reviewer B:
This introduction to membrane computing, written by Gh Paun, is an up-to-date account of the current state of this research area. The presentation is well-written and adequately structured. I have some suggestions regarding the presentation. In "A Quick Description..." section "comoartment" should be "compartment" and on the same line "in" and "out" should be written with the font utilised for rules. In the next paragraph, at the end, when "P colony" is mentioned, a reference might help. The first sentence of "Power and Efficiency" is too long and hard to comprehend - some shorter sentences will explain better the message. The end of the third sentence, ".. and other operations.." does not fit within this context. In the next sentence "SN P systems" is used for the first time; better to introduce this in the previous section when Spiking neural P systems are mentioned. In the "Applications" section: a space between "proces" and "("; "There also are" -> "There are also"; "from mathematical theory" -> "from the mathematical theory".
