Membrane computing

Membrane computing

Membrane computing is an area within computer science that seeks to discover new computational models 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.[1]

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.

See also

  • Modeling biological systems

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Membrane keyboard — as used on the East German Robotron Z1013. A membrane keyboard is a computer keyboard whose keys are not separate, moving parts, as with the majority of other keyboards, but rather are pressure pads that have only outlines and symbols printed on… …   Wikipedia

  • Natural computing — For the scientific journal, see Natural Computing (journal). Natural computing, also called Natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of… …   Wikipedia

  • Biologically-inspired computing — Biologically inspired (often hyphenated as biologically inspired) computing (also bio inspired computing) is a field of study that loosely knits together subfields related to the topics of connectionism, social behaviour and emergence. It is… …   Wikipedia

  • Keyboard (computing) — In computing, a keyboard is an input device partially modelled after the typewriter keyboard which uses an arrangement of buttons, or keys which act as electronic switches. A keyboard typically has characters engraved or printed on the keys, and… …   Wikipedia

  • Mobile Membranes — Membrane systems have been inspired from the structure and the functioning of the living cells. They were introduced and studied by Gh.Paun under the name of P systems [24]; some applications of the membrane systems are presented in [15].… …   Wikipedia

  • P system — For the computer p System, see UCSD 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,… …   Wikipedia

  • Morphological computation (robotics) — Morphological computation is computation obtained through interactions of physical form. Contents 1 Birth of the term morphological computation 2 Relevance 2.1 Robotics 2.2 Artificial intellige …   Wikipedia

  • Modelling biological systems — Modeling biological systems is a significant task of systems biology and mathematical biology. Computational systems biology aims to develop and use efficient algorithms, data structures, visualization and communication tools with the goal of… …   Wikipedia

  • Cellular model — Part of the Cell Cycle 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… …   Wikipedia

  • Computational model — For mathematical models of computers, see Model of computation. 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… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”