28-06-2012, 04:33 PM
membrane computing
seminar report on membrane computing.docx (Size: 193.12 KB / Downloads: 40)
INTRODUCTION
This is well known that the cell is the smallest thing on earth to be unanimously considered as live. The cell has a very exquisite internal structure. It is composed of compartments created by various membranes. An outer membrane defines the cell itself from the environment. The membrane is a semi-permeable barrier between the compartments. Molecules can be transported from one compartment to other via vesicles enclosed by membranes. The membrane structure is hierarchical. The compartments are like “protected reactors” where specific biochemical processes take place.
Our membrane computing model is roughly inspired by these properties of the cell and its internal membrane structure. Membrane computing is an area of computer science aiming to abstract computing ideas and models from the structure and the functioning of living cells, as well as from the way the cells are organized in tissues or higher order structures.
The main component of this model is the P system or membrane structure. The area of membrane systems was triggered by a landmark paper by Gheoghe Paun in 1998 (whose last name is the origin of latter P in ‘P System’) in the Turku Centre for Computer Science (TUCS) Report. Each membrane of this structure defines a region. Each region has a multiset of objects. And each region has a set of rules (evolution rules or symport / antiport rules) which operate on the multiset of objects in that region. Evolution rules are rewriting rules (like grammar rules) that represent the biochemical reactions going on in the cell-compartments and symport/antiport rules are transport rules that represent the vesicles through which molecules are transported from one compartment to other. The result of a computation can be the number of objects of a particular kind in a region (called output region), though there are other possibilities, too. The intuition behind the notion of a membrane is that from biology, of a three–dimensional vesicle, but the concept itself is generalized/idealized to interpreting a membrane as a separator of two regions (of the Euclidean space), a finite “inside” and an infinite “outside”, also providing the possibility of a selective communication among the two regions.
THE MEMBRANE STRUCTURE
The central notion of membrane computing is the notion of membrane understood as a three-dimensional vesicle, which geometrically can be considered as a ball in the Euclidean space. Thus a membrane delimits a space, separating in this way “inside” from “outside”. The (inside) space delimited by a membrane serves as a “protected reactor”—a space where specific reactions take place, using molecules in this space.
Inspired by the structure of the living cell, in our basic model we will consider hierarchical arrangements of finite number of membranes, with membranes nested within other membranes (hence the balls in the space included within other balls). In this chapter, unless indicated otherwise, we will deal with such cell-like membrane structures (referred to simply as membrane structures).
We will introduce now, rather informally, a number of notions which are useful in discussing membrane structures.
RULES OF MEMBRANE COMPUTING
Evolution Rule
In the basic variant of P systems, each region contains a multiset of symbol-objects, which correspond to the chemicals swimming in a solution in a cell compartment; these chemicals are considered here as unstructured, that is why we describe them by symbols from a given alphabet.
The objects evolve by means of evolution rules, which are also localized, associated with the regions of the membrane structure. Actually, there are different types of rules:
(1) Multiset rewriting rules
(2) Communication rules
Cell-like P Systems with Communication Rules
A P system with communication rules is defined in a similar fashion to a P system with multiset rewriting rules, but with some essential differences. First of all, we consider now communication rules rather than rewriting rules—sets of such rules are associated with membranes rather than with regions. Moreover, since there are communication rules only, one needs a supply of objects that can be moved into the system. Otherwise, the multiset of objects present in the system will never change and consecutive configurations of a computation would present merely distributions of this fixed multiset through the regions of the system. Such a supply is ensured by specifying a subset E of the set of all objects O, and assuming that objects from E are available in the environment in arbitrary multiplicities (thus their multiset is M : E −→ { ∞ } ).