Membrane computing
Encyclopedia
Membrane computing is an area within computer science
that seeks to discover new computational model
s from the study of biological cells
, particular of the cellular membranes. It is a sub-task of creating a cellular model
.
Membrane computing or MC deals with distributed and parallel computing models, processing multisets of symbol objects in a localized manner. Thus, evolution rules and evolving objects are encapsulated into compartments defined by membranes. The communications between compartments and with the environment play an essential role in the processes. The various types of membrane systems are known as P systems after Gheorghe Păun
who first conceived the model in 1998.
An essential ingredient of a P system
is its membrane structure, which can be a hierarchical arrangement of membranes, as in a cell, or a net of membranes (placed in the nodes of a graph), as in a tissue or a neural net. P systems are often depicted graphically with drawings.
The intuition behind the notion of a membrane is a three-dimensional vesicle from biology. However the concept itself is more general, and a membrane is seen as a separator of two regions. The membrane provides for selective communication between the two regions. As per George Paun, the separation is of the Euclidean space
into a finite “inside” and an infinite “outside”. The selective communication is where the computing comes in.
Graphical representations may have numerous elements, according to the variation of the model that is being studied. For example, a rule may produce the special symbol δ, in which case the membrane that contains it is dissolved and all its contents move up in the region hierarchy.
The variety of suggestions from biology and the range of possibilities to define the architecture and the functioning of a membrane-based multiset processing device are practically endless, and already the literature of MC contains a very large number of models. Thus, MC is not merely a theory related to a specific model, it is a framework for devising compartmentalized models.
Chemicals are modeled by symbols, or alternatively by strings of symbols. The region, which is defined by a membrane, can contain other symbols or strings (collectively referred to as objects) or other membranes, so that a P system
has exactly one outer membrane, called the skin membrane, and a hierarchical relationship governing all its membranes under the skin membrane.
If objects are symbols, then their multiplicity within a region matters; however multi-sets are also used in some string models. Regions have associated rules that define how objects are produced, consumed, passed to other regions and otherwise interact with one another. The nondeterministic maximally parallel application of rules throughout the system is a transition between system states, and a sequence of transitions is called a computation. Particular goals can be defined to signify a halting state, at which point the result of the computation would be the objects contained in a particular region. Alternatively the result may be made up of objects sent out of the skin membrane to the environment.
Many variant models have been studied, and the main interest has been focused on proving computational universality for systems with a small number of membranes, for the purpose of solving NP-complete problems such as Boolean satisfiability (SAT) problems
and the traveling salesman problem (TSP)
. The P systems may trade space and time complexities and less often use models to explain natural processes in living cells. The studies devise models that may at least theoretically be implemented on hardware. However, to date, the P systems are all theoretical models that have never been reduced to practice.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
that seeks to discover new computational model
Computational model
A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation. The system under study is often a complex nonlinear system for which simple, intuitive analytical solutions are...
s from the study of biological cells
Cell (biology)
The cell is the basic structural and functional unit of all known living organisms. It is the smallest unit of life that is classified as a living thing, and is often called the building block of life. The Alberts text discusses how the "cellular building blocks" move to shape developing embryos....
, particular of the cellular membranes. It is a sub-task of creating a cellular model
Cellular model
Creating a cellular model has been a particularly challenging task of systems biology and mathematical biology.It involves developing efficient algorithms, data structures, visualization and communication tools to orchestrate the integration of large quantities of biological data with the goal of...
.
Membrane computing or MC deals with distributed and parallel computing models, processing multisets of symbol objects in a localized manner. Thus, evolution rules and evolving objects are encapsulated into compartments defined by membranes. The communications between compartments and with the environment play an essential role in the processes. The various types of membrane systems are known as P systems after Gheorghe Păun
Gheorghe Paun
Gheorghe Păun is a computer scientist from Romania, prominent for work on membrane computing and the P system.Păun studied mathematics at the University of Bucharest, obtaining an MSc. in 1974 and a PhD in 1977. He has been a researcher at the Institute of Mathematics of the Romanian Academy since...
who first conceived the model in 1998.
An essential ingredient of a P system
P system
A P system is a computational model in the field of computer science that performs calculations using a biologically-inspired process. They are based upon the structure of biological cells, abstracting from the way in which chemicals interact and cross cell membranes...
is its membrane structure, which can be a hierarchical arrangement of membranes, as in a cell, or a net of membranes (placed in the nodes of a graph), as in a tissue or a neural net. P systems are often depicted graphically with drawings.
The intuition behind the notion of a membrane is a three-dimensional vesicle from biology. However the concept itself is more general, and a membrane is seen as a separator of two regions. The membrane provides for selective communication between the two regions. As per George Paun, the separation is of the Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
into a finite “inside” and an infinite “outside”. The selective communication is where the computing comes in.
Graphical representations may have numerous elements, according to the variation of the model that is being studied. For example, a rule may produce the special symbol δ, in which case the membrane that contains it is dissolved and all its contents move up in the region hierarchy.
The variety of suggestions from biology and the range of possibilities to define the architecture and the functioning of a membrane-based multiset processing device are practically endless, and already the literature of MC contains a very large number of models. Thus, MC is not merely a theory related to a specific model, it is a framework for devising compartmentalized models.
Chemicals are modeled by symbols, or alternatively by strings of symbols. The region, which is defined by a membrane, can contain other symbols or strings (collectively referred to as objects) or other membranes, so that a P system
P system
A P system is a computational model in the field of computer science that performs calculations using a biologically-inspired process. They are based upon the structure of biological cells, abstracting from the way in which chemicals interact and cross cell membranes...
has exactly one outer membrane, called the skin membrane, and a hierarchical relationship governing all its membranes under the skin membrane.
If objects are symbols, then their multiplicity within a region matters; however multi-sets are also used in some string models. Regions have associated rules that define how objects are produced, consumed, passed to other regions and otherwise interact with one another. The nondeterministic maximally parallel application of rules throughout the system is a transition between system states, and a sequence of transitions is called a computation. Particular goals can be defined to signify a halting state, at which point the result of the computation would be the objects contained in a particular region. Alternatively the result may be made up of objects sent out of the skin membrane to the environment.
Many variant models have been studied, and the main interest has been focused on proving computational universality for systems with a small number of membranes, for the purpose of solving NP-complete problems such as Boolean satisfiability (SAT) problems
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
and the traveling salesman problem (TSP)
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
. The P systems may trade space and time complexities and less often use models to explain natural processes in living cells. The studies devise models that may at least theoretically be implemented on hardware. However, to date, the P systems are all theoretical models that have never been reduced to practice.