Mobile membranes information

This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (August 2018) (Learn how and when to remove this message)

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]. Membrane systems are essentially models of distributed, parallel and nondeterministic systems. Here we motivate and present the mobile membranes. Mobile membranes represent a variant of membrane systems inspired by the biological movements given by endocytosis and exocytosis. They have the expressive power of both P systems and process calculi with mobility such as mobile ambients [11] and brane calculi [10]. Computations with mobile membranes can be defined over specific configurations (like process calculi), while they represent also a rule-based formalism (like P systems).

The model is characterized by two essential features:

• A spatial structure consisting of a hierarchy of membranes (which do not intersect) with objects associated to them. A membrane without any other membranes inside is called elementary.
• The general rules describing the evolution of the structure: endocytosis (moving an elementary membrane inside a neighbouring membrane) and exocytosis (moving an elementary membrane outside the membrane where it is placed). More specific rules are given by pinocytosis (engulfing zero external membranes) and phagocytosis (engulfing just one external elementary membrane).

The computations are performed in the following way: starting from an initial structure, the system evolves by applying the rules in a nondeterministic and maximally parallel manner. A rule is applicable when all the involved objects and membranes appearing in its left hand side are available. The maximally parallel way of using the rules means that in each step a maximal multiset of rules is applied, namely a multiset of rules such that no further rule can be added to the set. A halting configuration is reached when no rule is applicable. The result is represented by the number of objects associated to a specified membrane.

Mobile membranes represents a formalism which describes the movement of membranes inside a spatial structure by applying rules from a given set of rules ${\displaystyle R}$. The mobility is provided by consumption and rewriting of objects. In terms of computation, the work is performed using membrane configurations. A the set ${\displaystyle {\mathcal {M}}}$ of membrane configurations (ranged by ${\displaystyle M,N,\dots }$) os defined by using the free monoid ${\displaystyle V^{*}}$ (ranged over by ${\displaystyle u,v,\dots }$) generated by a finite alphabet ${\displaystyle V}$ (ranged over by ${\displaystyle a,b,\dots }$):

${\displaystyle \qquad \qquad M::=u\;\mid \;[\;M\;]_{u}\;\mid \;M\|M}$

If ${\displaystyle M}$ and ${\displaystyle N}$ are two membrane configurations, ${\displaystyle M}$ reduces to ${\displaystyle N}$ (denoted by ${\displaystyle M\rightarrow N}$) if there exists a rule in the set of rules ${\displaystyle R}$ applicable to the configuration ${\displaystyle M}$ such that the new configuration ${\displaystyle N}$ is obtained. When applying the rules of ${\displaystyle R}$, also the following inference rules are used:

${\displaystyle \qquad {\it {(Comp1)}}\quad {\frac {\displaystyle M\ \rightarrow \ M'}{\displaystyle M\|N\ \rightarrow \ M'\|N}};\qquad \qquad {\it {(Comp2)}}\quad {\frac {\displaystyle M\ \rightarrow \ M'\qquad \displaystyle N\ \rightarrow \ N'}{\displaystyle M\|N\ \rightarrow \ M'\|N'}}}$;

${\displaystyle \qquad {\it {(Mem)}}\ {\frac {\displaystyle M\ \rightarrow \ M'}{\displaystyle [\;M\;]_{u}\rightarrow [\;M'\;]_{u}}};\qquad \qquad {\it {(Struc)}}\ {\frac {\displaystyle M\equiv _{mem}M'\quad M'\rightarrow N'\quad \ N'\equiv _{mem}N}{\displaystyle M\rightarrow N}}}$

When describing a computation of a systems of mobile membranes, an initial configuration ${\displaystyle M_{0}}$ and a set of rules ${\displaystyle R}$ are given. The rules used in this paper describe an ${\displaystyle {\it {object~evolution}}}$ (object rewriting), ${\displaystyle {\it {endocytosis}}}$ movement (moving an elementary membrane inside a neighbouring membrane), ${\displaystyle {\it {exocytosis}}}$ movement (moving an elementary membrane outside the membrane where it is placed), ${\displaystyle {\it {pinocytosis}}}$ (engulfing zero external membranes), and ${\displaystyle {\it {phagocytosis}}}$ (engulfing just one external elementary membrane).