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]. 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 $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 ${\mathcal {M}}$ of membrane configurations (ranged by $M,N,\dots$) os defined by using the free monoid $V^{*}$ (ranged over by $u,v,\dots$) generated by a finite alphabet $V$ (ranged over by $a,b,\dots$):

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

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

$\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'}}$;

$\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 $M_{0}$ and a set of rules $R$ are given. The rules used in this paper describe an ${\it {object~evolution}}$ (object rewriting), ${\it {endocytosis}}$ movement (moving an elementary membrane inside a neighbouring membrane), ${\it {exocytosis}}$ movement (moving an elementary membrane outside the membrane where it is placed), ${\it {pinocytosis}}$ (engulfing zero external membranes), and ${\it {phagocytosis}}$ (engulfing just one external elementary membrane).

Computability Power of Mobile Membranes

A specific feature of the mobile membranes is that this new rule-based model is appropriate to prove computability results in terms of Turing machines rather by reduction to the lambda calculus as in the case of process calculi with mobility. In this section are defined four classes of membranes inspired from biological facts, and it is shown that their computational power depends on the initial configuration and on the set of rules used.

Simple Mobile Membranes

The systems of simple mobile membranes (SM) are defined over the set of configurations ${\mathcal {M}}$, and evolve using endocytosis and exocytosis rules, namely moving a membrane inside a neighbouring membrane, or outside the membrane where it is placed, respectively. The evolution from a configuration to another is made using rules from the set of rules $R$ defined as follows:

$[[a\;\|\;M]_{m}\;\|\;N]_{k}\rightarrow [[v\;\|\;M]_{m}\;\|\;N]_{k}$, for $k,m\in {\mathcal {N}}$, $a\in V$, $v\in V^{*}$; (local object evolution)

$[a\;\|\;M]_{m}\rightarrow [v\;\|\;M]_{m}$, for $m\in {\mathcal {N}}$, $a\in V$, $v\in V^{*}$; (global object evolution)

$[a\;\|\;M_{1}]_{h}\;\|\;[M]_{m}\rightarrow [[b\;\|\;M_{1}]_{h}\;\|\;M]_{m}$, for $h,m\in {\mathcal {N}}$, $a,b\in V$; (endocytosis)

$[[a\;\|\;M_{1}]_{h}\;\|\;M]_{m}\rightarrow [b\;\|\;M_{1}]_{h}\;\|\;[M]_{m}$, for $h,m\in {\mathcal {N}}$, $a,b\in V$; (exocytosis)

where $M_{1}$ is a multiset, and $M$, $N$ are arbitrary membrane configurations.

Turing completeness can be obtained by using nine membranes together with the operations of endocytosis and exocytosis [21]. In [17] it is proven that four mobile membranes are enough to get the power of a Turing machine, while in [4] the number of membranes is decreased to three.

$SM(levol,endo,exo)$ denotes the family of all sets generated inside a given membrane by simple mobile membranes using local evolution rules ($levol$), endocytosis and exocytosis rules. Whenever global evolution rules ($gevol$) are used, the parameter $levol$ is replaced by $gevol$. If a type of rules is not used, then its name is omitted from the list. The number of membranes does not increase during the computation, but it can decrease by sending membranes out of the system. In this case, the $SM_{n}(gevol,endo,exo)$ denotes the family of sets of vectors of natural numbers computed by using at most $n$ membranes. $RE$ denoted the family of Turing computable sets of vectors generated by arbitrary grammars.

It is proved in [17] that $SM_{4}(gevol,endo,exo)=RE$. The research line initiated in membrane computing is to find membrane systems with a minimal set of ingredients which are powerful enough to achieve the full power of Turing machines. In this way previous result presented in [17] are improved by decreasing the number of membranes to three. Moreover, this is achieved by using local evolution rules instead of global evolution rules.

Theorem. $SM_{3}(levol,endo,exo)=RE$.

The proof of this result uses a similar technique to that used in [4].

Enhanced Mobile Membranes

The systems of enhanced mobile membranes are a variant of simple membrane systems proposed in [1] for describing some biological mechanisms of the immune system. The operations governing the mobility of the systems of enhanced mobile membranes are endocytosis (endo), exocytosis (exo), forced endocytosis (fendo), forced exocytosis (fexo).The evolution from a configuration to another is made using rules from the set of rules $R$ defined as follows:

$[u\;\|\;v\;\|\;M]_{h}\;\|\;[v'\;\|\;N]_{m}\!\rightarrow \![w'\;\|\;[w]_{h}]_{m}$ for $h,m\!\in \!{\mathcal {N}};u\!\in \!V^{+},v,v',w,w'\!\in \!V^{*}$; (endocytosis)

$[v'\;\|\;N\;\|\;[u\;\|\;v\;\|\;M]_{h}]_{m}\!\rightarrow \![w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}$, for $h,m\!\in \!\!{\mathcal {N}};u\in V^{+},v,v',w,w'\in V^{*}$; (exocytosis)

$[v\;\|\;M]_{h}\;\|\;[u\;\|\;v'\;\|\;N]_{m}\!\!\rightarrow \!\![[w\;\|\;M]_{h}\;\|\;w'\;\|\;N]_{m}$ for $h,m\!\!\in \!\!{\mathcal {N}}$, $u\!\in \!V^{+},v,v'\!,w,w'\!\in \!V^{*}$; (enhanced endocytosis)

$[u\;\|\;v'\;\|\;[v\;\|\;M]_{h}\;\|\;N]_{m}\!\!\rightarrow \!\![w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}$ for $h,m\!\in \!{\mathcal {N}},u\in V^{+},v,v',w,w'\in V^{*}$;(enhanced exocytosis)

\noindent where $M$ is a multiset and $N$ is an arbitrary membrane configuration.

The computational power of the systems of enhanced mobile membranes using these four operations was studied in [20] where it is proved that twelve membranes can provide the computational universality, while in [4] the result is improved by reducing the number of membranes to nine. It is worth to note that unlike the previous results, the rewriting of object by means of context-free rules is not used in any of the results (and their proofs).

The interplay between these four operations is quite powerful, and the computational power of a Turing machine is obtained using twelve membranes without using the context-free evolution of objects [20].

The family of all sets generated inside a given membrane by enhanced mobile membranes of degree at most $n$ using rules $\alpha \subseteq \{exo,endo,fendo,fexo\}$, is denoted by $EM_{n}(\alpha )$.

Theorem. $EM_{3}(endo,exo)=EM_{3}(fendo,fexo)$.

Theorem. $EM_{12}(endo,exo,fendo,fexo)=RE$.

When proving the result of the previous theorem the authors have not used an optimal construction of a membrane system. In what follows it is proven that using the same types of rules (endo, exo, fendo, fexo) a membrane system can be constructed using only nine membranes instead of twelve membranes. If this is an optimal construction remains an open problem.

Theorem. $EM_{9}(endo,exo,fendo,fexo)=RE$.

The proof is similar to that presented in [4].

Mutual Mobile Membranes

Following the approach presented in [3], "systems of mutual mobile membranes" representing a variant of systems of simple mobile membranes in which the endocytosis and the exocytosis work whenever the involved membranes "agree" on the movement are defined; this agreement is described by using dual objects $a$ and ${\overline {a}}$ in the involved membranes. The operations governing the mobility of the systems of mutual mobile membranes are mutual endocytosis (mutual endo), and mutual exocytosis (mutual exo). The evolution from a configuration to another is made using rules from the set of rules $R$ defined as follows:

$[u\;\|\;v\;\|\;M]_{h}\;\|\;[{\overline {u}}\;\|\;v'\;\|\;N]_{m}\rightarrow [\;[w\;\|\;M]_{h}\;\|\;w'\;\|\;N]_{m}$ for $h,m\in {\mathcal {N}},u,{\overline {u}}\in V^{+},v,v',w,w'\!\!\in V^{*}$; (mutual endocytosis)

$[{\overline {u}}\;\|\;v'\;\|\;N\;\|\;[u\;\|\;v\;\|\;M]_{h}]_{m}\rightarrow [w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}$ for $h,m\in {\mathcal {N}},u,{\overline {u}}\in V^{+},v,v',w,w'\!\!\in V^{*}$; (mutual exocytosis)

where $M$ is a multiset and $N$ is an arbitrary membrane configuration.

It is enough to consider the biologically inspired operations of mutual endocytosis and mutual exocytosis and three membranes to get the full computational power of a Turing machine [6]. Three also represents the minimum number of membranes in order to discuss properly about the movement provided by endocytosis and exocytosis: working with configurations corresponding to a system of two membranes moving inside a skin membrane.

The family of all sets generated inside a given membrane by mutual mobile membranes of degree $n$ using mutual endocytosis rules (mendo) and mutual exocytosis rules (mexo) is denoted by $MM_{n}(mendo,mexo)$. Therefore, the result can be formulated as following.

Theorem. $MM_{3}(mendo,mexo)=RE$.

In systems of simple mobile membranes with local evolution rules and mobility rules it is known that systems of degree three have the same power as a Turing machine, while in systems of enhanced mobile membranes using only mobility rules the degree of systems having the same power as a Turing machine increases to nine. In each mobility rule from systems of simple and enhanced mobile membranes, in the left hand side of the rules only one object appears in the proofs. By using multisets instead of objects and synchronization by objects and co-objects, it is proved that it is enough to consider only systems of three mutual mobile membranes together with the operations of mutual endocytosis and mutual exocytosis to get the full computational power of a Turing machine.

The proof is done in a similar manner with the proof for the computational universality of the systems of enhanced mobile membranes [20].

Mutual Membranes with Objects on Surface

Membrane systems [24] and brane calculus [10] start from the same observations; however, they are built having in mind different goals: membrane systems investigate formally the computational nature and power of various features of membranes, while the brane calculus is capable to give a faithful and intuitive representation of the biological reality. In [12] the initiators of these two formalisms describe the goals they had in mind: "While membrane computing is a branch of natural computing which tries to abstract computing models, in the Turing sense, from the structure and the functioning of the cell, making use especially of automata, language, and complexity theoretic tools, brane calculi pay more attention to the fidelity to the biological reality, have as a primary target systems biology, and use especially the framework of process~algebra."

In [2] are defined systems of mutual membranes with objects on surface, following the idea of adding objects on membrane and using the biologically inspired rules pino/exo/phago coming from [12,14,18,19]. Objects and co-objects are used in phago and exo rules in order to illustrate the fact that both involved membranes agree on the movement. The evolution from a configuration to another is made using rules from the set of rules $R$ defined as follows:

$[M]_{v\;\|\;a\;\|\;u}\rightarrow [[~]_{u\;\|\;x}\;\|\;M]_{v\;\|\;y}$, for $a\in V,u,v,x,y\in V^{*},ux,vy\in V^{+}$ (pino)

$[[M]_{a\;\|\;u}\;\|\;N]_{{\overline {a}}\;\|\;v}\rightarrow M\;\|\;[N]_{u\;\|\;v\;\|\;x}$, for a$,{\overline {a}}\in V,u,v,x\in V^{*},uvx\in V^{+}$ (exo)

$[M_{1}]_{a\;\|\;u}\;\|\;[N]_{{\overline {a}}\;\|\;b\;\|\;v}\rightarrow [[[M_{1}]_{u\;\|\;x}]_{b}\;\|\;N]_{v\;\|\;y}$, for $a,{\overline {a}},b\!\in \!V,u,v,x,y\in V^{*},ux,vy\in V^{+}$ (phago)

\noindent where $M_{1}$ is a multiset and $M$, $N$ are arbitrary membrane configurations.

The computational power of systems of mutual membranes with objects on surface controlled by pairs of rules is investigated: pino/exo or phago/exo, proving that they are universal even using a small number of membranes. These cases were already investigated in [19]; however better results are provided by improving the number of membranes. A summary of the results (existing and new ones) is given in what follows:

Summary of Results

---

Operations	$\qquad$Number of membranes	$\qquad$Weight	$\qquad$RE	$\qquad$Where
Pino, exo	8	4,3	Yes	Theorem 6.1 [19]
Pino, exo	3	5,4	Yes	Here
Phago, exo	9	5,2	Yes	Theorem 6.2 [19]
Phago, exo	9	4,3	Yes	Theorem 6.2 [19]
Phago, exo	4	6,3	Yes	Here

The multiplicity vector of the multiset from all membranes is considered as a result of the computation. Thus, the result of a halting computation consists of all the vectors describing the multiplicity of objects from all the membranes; a non-halting computation provides no output. The number of objects from the right-hand side of a rule is called its weight. The family of all sets generated by systems of mutual membranes with objects on surface using at any moment during a halting computation at most $n$ membranes, and any of the rules $r_{1},r_{2}\in \{pino,exo,phago\}$ of weight at most $r,s$ respectively, is denoted by $MMOS_{n}(r_{1}(r),r_{2}(s)$). When one of the parameters is not bounded, it is replaced it with a $*$.

It is proven in [19] that systems of eight membranes with objects on surface and using pino and exo operations of weight four and three are universal. The number of membranes can be reduced from eight to three. However, in order to do this is increased the weight of the pino and exo operations with one, namely from four and three to five and four. This means that in order to construct a universal system of mobile membranes with objects on surface by using pino and exo operations, one needs to decide either he wants to minimize the number of membranes, or the weights of the operations.

Theorem. $MMOS_{m}(pino(r),exo(s))=RE$, for all $m\geq 3,r\geq 5,s\geq 4$.

It is proven in [19] that systems of nine membranes with objects on surface and using phago and exo operations of weight four and three (or five and two) are universal. The number of membranes can be reduced from nine to four, but in order to do this the weight of the phago and exo operations are increased from four and three (or five and two) to six and three. When constructing a Turing complete system of mobile membranes with objects on surface by using phago and exo operations, the same problem appears as when using pino and exo operations: namely, to choose either minimizing the number of membranes, or the weights of the operations.

Theorem. $MMOS_{m}(phago(r),exo(s))=RE$, for all $m\geq 4,r\geq 6,s\geq 3$.

Expressive Power of Mobile Membranes

In what follows it is shown that mobile membranes have at least the expressive power of mobile ambients and brane calculi by encoding mobile ambients and brane calculi in certain systems of mobile membranes.

Embedding Mobile Ambients into Mobile Membranes

The mobile membranes and the mobile ambients [11] have similar structures and common concepts. Both have a hierarchical structure representing locations, intend to describe mobility, and are used in describing various biological phenomena [10,15]. The mobile ambients are suitable to represent the movement of ambients through ambients and the communication which takes place inside the boundaries of ambients. Membrane systems are suitable to represent the evolution of objects and movement of objects and membranes through membranes. A comparing between these new models (mobile ambients and mobile membranes) is provided, and an encoding the ambients into membranes. This embedding is essentially presented in [5].

Safe ambients represent a variant of mobile ambients in which any movement of an ambient takes place only if both participants agree. The mobility is provided by the consumption of certain pairs of capabilities. The safe ambients differ from mobile ambients by the addition of co-actions: if in mobile ambients a movement is initiated only by the moving ambient and the target ambient has no control over it, in safe ambients both participants must agree by using a matching between action and co-action. A short description of pure safe ambients (SA) is given below; more information can be found in [22,23]. Given an infinite set of names ${\mathcal {N}}$ (ranged over by $m,n,\dots$), the set ${\mathcal {A}}$ of SA-processes (denoted by $A,A',B,B',\dots$) together with their capabilities (denoted by $C,C',\dots$) are defined as follows:

$\qquad C::=in\ n\;\mid \;{\overline {in}}\ n\;\mid \;out\ n\;\mid \;{\overline {out}}\ n\;\mid \;open\ n\;\mid \;{\overline {open}}\ n$

$\qquad A::=0\quad \mid \quad A\;\mid \;B\quad \mid \quad C.A\quad \mid \quad n[\;A\;]$

Process $0$ is an inactive mobile ambient. A movement $C.\,A$ is provided by the capability $C$, followed by the execution of $A$. An ambient $n[\;A\;]$ represents a bounded place labelled by $n$ in which a SA-process $A$ is executed. $A\,\mid \,B$ is a parallel composition of mobile ambients $A$ and $B$. $(\nu n)A$ creates a new unique name $n$ within the scope of $A$. The structural congruence $\equiv _{amb}$ over ambients is the least congruence such that $({\mathcal {A}},\mid ,0)$ is a commutative monoid.

The operational semantics of pure ambient safe calculus are defined in terms of a reduction relation $\Rightarrow _{amb}$ by the following axioms and rules.

Axioms:

$(In)\quad n[\;in\ m.A\mid A'\;]\mid m[\;{\overline {in}}\ m.B\mid B'\;]\Rightarrow _{amb}m[\;n[\;A\mid A'\;]\mid B\mid B'\;]$;

$(Out)\quad m[\;n[\;out\ m.A\mid A'\;]\mid {\overline {out}}\ m.B\mid B'\;]\Rightarrow _{amb}n[\;A\mid A'\;]\mid m[\;B\mid B'\;]$;

$(Open)\quad open\ n.A\;\mid \;n[\;{\overline {open}}\ n.B\mid B'\;]\Rightarrow _{amb}A\;\mid \;B\;\mid \;B'$.

Rules:

$(Comp1)\quad {\frac {\displaystyle A\Rightarrow _{amb}A'}{\displaystyle A\;\mid \;B\Rightarrow _{amb}A'\;\mid \;B}};\qquad \qquad \qquad \qquad (Comp2)\quad {\frac {\displaystyle A\Rightarrow _{amb}A'\quad \displaystyle B\Rightarrow _{amb}B'}{\displaystyle A\;\mid \;B\Rightarrow _{amb}A'\;\mid \;B'}}$;

$(Amb)\quad {\frac {\displaystyle A\Rightarrow _{amb}A'}{\displaystyle n[\;A\;]\Rightarrow _{amb}n[\;A'\;]}};\qquad \qquad \qquad \qquad (Struc)\quad {\frac {\displaystyle A\equiv A',\ A'\Rightarrow _{amb}B',\ B'\equiv B}{\displaystyle A\Rightarrow _{amb}B}}$.

$\Rightarrow _{amb}^{*}$ denotes a reflexive and transitive closure of the binary relation $\Rightarrow _{amb}$.

A translation from the set ${\mathcal {A}}$ of safe ambients to the set ${\mathcal {M}}$ of membrane configurations is given formally as follows:

Definition. A translation ${\mathcal {T}}:{\mathcal {A}}\rightarrow {\mathcal {M}}$ is given by ${\mathcal {T}}(A)=dlock~{\mathcal {T}}_{1}(A)$, where ${\mathcal {T}}_{1}:{\mathcal {A}}\rightarrow {\mathcal {M}}$ is

$\qquad {\mathcal {T}}_{1}(A)=$${\begin{cases}cap~n\;\|\;[~]_{cap~n}&{\mbox{if }}A=cap~n\\cap~n\;\|\;[\;{\mathcal {T}}_{1}(A_{1})\;]_{cap~n}&{\mbox{if }}A=cap~n.\,A_{1}\\\;[\;{\mathcal {T}}_{1}(A_{1})\;]_{n}&{\mbox{if }}A=n[\;A_{1}\;]\\\;[~]_{n}&{\mbox{if }}A=n[~]\\{\mathcal {T}}_{1}(A_{1})\;\|\;{\mathcal {T}}_{1}(A_{2})&{\mbox{if }}A=A_{1}\,\mid \,A_{2}\\\lambda &{\mbox{if }}A=0\end{cases}}$

An object $dlock$ is placed near the membrane structure to prevent the consumption of capability objects in a membrane system which corresponds to a mobile ambient which cannot evolve further.

Proposition. Structurally congruent ambients are translated into structurally congruent membrane systems; moreover, structurally congruent translated membrane systems correspond to structurally congruent ambients: $\qquad \qquad A\equiv _{amb}B$ iff ${\mathcal {T}}(A)\equiv _{mem}{\mathcal {T}}(B)$.

Considering two membrane systems $M$ and $N$ with only one object $dlock$, $M\Rightarrow _{mem}N$ if there is a sequence of rules $r_{1},\ldots ,r_{i}$, from the particular set of rules used in [7], such that applying the rules from this set to the membrane configuration $M$ it is obtained the membrane configuration $N$.

Proposition. If $A$ and $B$ are two ambients and $M$ is a membrane system such that $A\Rightarrow _{amb}B$ and $M={\mathcal {T}}(A)$, then there exists a set of rules applicable to $M$ such that $M\Rightarrow _{mem}N$, and $N={\mathcal {T}}(B)$.

Proposition. Let $M$ and $N$ be two membrane systems with only one $dlock$ object, and an ambient $A$ such that $M={\mathcal {T}}(A)$. If there is a set of rules applicable to $M$ such that $M\Rightarrow _{mem}N$, then there exists an ambient $B$ with $A\Rightarrow _{amb}^{*}B$ and $N={\mathcal {T}}(B)$. The number of pairs of non-star objects consumed in membrane systems is equal with the number of pairs of capabilities consumed in ambients.

Theorem. (Operational correspondence)

• If $A\Rightarrow _{amb}B$, then ${\mathcal {T}}(A)\Rightarrow _{mem}{\mathcal {T}}(B)$.
• If ${\mathcal {T}}(A)\Rightarrow _{mem}M$, then exists $B$ such that $A\Rightarrow _{amb}B$ and $M={\mathcal {T}}(B)$.

Embedding Brane Calculus into Mobile Membranes

A fragment of brane calculus called PEP, and mutual mobile membranes with objects on surface as a variant of systems with mobile membranes are considered. The mobile membranes with objects on surface is inspired by a model of membrane system introduced in [12] having objects attached to membranes. A simulation of the PEP fragment of brane calculus by using mutual membranes with objects on surface is presented. This approach is related to some other papers trying to show the relationship between membrane systems and brane calculus [8,9,14,18,19].

As it is expressed in [24], "at the first sight the role of objects placed on membranes is different in membrane and brane systems: in membrane computing the focus is on the evolution of objects themselves, while in brane calculi the objects ("proteins") mainly control the evolution of membranes". By defining an encoding of the PEP fragment of brane calculus into mutual membranes with objects on surface, it is shown that the difference between the two models is not significant. Another difference regarding the semantics of the two formalisms is expressed in [8]: "whereas brane calculi are usually equipped with an interleaving, sequential semantics (each computational step consists of the execution of a single instruction), the usual semantics in membrane computing is based on maximal parallelism (a computational step is composed of a maximal set of independent interactions)".

Brane calculus [10] deals with membranes representing the sites of activity; thus a computation happens on the membrane surface. The operations of the two basic brane calculi, pino, exo, phago (PEP) and mate, drip, bud (MBD) are directly inspired by biologic processes such as endocytosis, exocytosis and mitosis. The latter operations can be simulated using the formers one [10].

Pino/Exo/Phage Calculus - Its Syntax

---

Systems	$P,Q$	$::\,=$	$P\circ Q\;\mid \;\sigma (~)\;\mid \;\sigma (P)$	nests of membranes
Branes	$\sigma ,\tau$	$::\,=$	$O\;\mid \;\sigma \mid \tau \;\mid \;a.\sigma$	combinations of actions
Actions	$a,b$	$::\,=$	$n^{\searrow }\;\mid \;{\overline {n}}^{\searrow }(\sigma )\;\mid \;n^{\nwarrow }\;\mid \;{\overline {n}}^{\nwarrow }\;\mid \;pino(\sigma )$	phago $\searrow$, exo $\nwarrow$

Membranes are formed of patches, where a patch $s$ can be composed from other patches $s=s_{1}\;\mid \;s_{2}$. An elementary patch $s$ consists of an action $a$ followed, after the consumption of it, by another patch $s_{1}s=a.s_{1}$. Actions often come in complementary pairs which cause the interaction between membranes. The names $n$ are used to pair-up actions and co-actions. Cardelli motivates that the replication operator is used to model the notion of a "multitude" of components of the same kind, which is in fact a standard situation in biology [10]. The replicator operator is not used because a membrane system cannot be defined without knowing exactly the initial membrane structure. ${\mathcal {P}}$ denotes the set of brane systems defined above. Some abbreviations can be made: $a.0$ as $a$, $0(P)$ as $(P)$, and $0(~)$ as $(~)$.

The structural congruence relation is a way of rearranging the system such that the interacting parts come together, as illustrated in what follows:

Pino/Exo/Phage Calculus - Structural Congruence

---

$P\circ Q\equiv _{b}Q\circ P$	$\qquad \qquad$	$\sigma \;\mid \;\tau \equiv _{b}\tau \;\mid \;\sigma$
$P\circ (Q\circ R)\equiv _{b}(P\circ Q)\circ R$	$\qquad \qquad$	$\sigma \;\mid \;(\tau \;\mid \;\rho )\equiv _{b}(\sigma \;\mid \;\tau )\;\mid \;\rho$
$\qquad$	$\qquad \qquad$	$\sigma \;\mid \;0\equiv _{b}\sigma$
$\qquad$	$\qquad \qquad$	$\qquad$
$P\equiv _{b}Q{\mbox{implies }}P\circ R\equiv _{b}Q\circ R$	$\qquad \qquad$	$\sigma \equiv _{b}\tau {\mbox{implies }}\sigma \;\mid \;\rho \equiv _{b}\tau \;\mid \;\rho$
$P\equiv _{b}Q{\mbox{and }}\sigma \equiv _{b}\tau {\mbox{implies }}\sigma (P)\equiv _{b}\tau (Q)$	$\qquad \qquad$	$\sigma \equiv _{b}\tau {\mbox{implies }}a.\sigma \equiv _{b}a.\tau$

In what follows the reduction rules of the calculus are presented:

Pino/Exo/Phago Calculus - Reduction Rules

---

$pino(\rho ).\sigma \mid \sigma _{0}(P)\rightarrow _{b}\sigma \mid \sigma _{0}(\rho (~)\circ P)$	$\qquad \qquad$	(Pino)
${\overline {n}}^{\nwarrow }.\tau \mid \tau _{0}(n^{\nwarrow }.\sigma \mid \sigma _{0}(P)\circ Q)\rightarrow _{b}P\circ \sigma \mid \sigma _{0}\mid \tau \mid \tau _{0}(Q)$	$\qquad \qquad$	(Exo)
$n^{\searrow }.\sigma \mid \sigma _{0}(P)\circ {\overline {n}}^{\searrow }(\rho ).\tau \mid \tau _{0}(Q)\rightarrow _{b}\tau \mid \tau _{0}(\rho (\sigma \mid \sigma _{0}(P))\circ Q)$	$\qquad \qquad$	(Phago)
$P\rightarrow _{b}Q{\mbox{implies }}P\circ R\rightarrow _{b}Q\circ R$	$\qquad \qquad$	(Par)
$P\rightarrow _{b}Q{\mbox{implies }}\sigma (P)\rightarrow _{b}\sigma (Q)$	$\qquad \qquad$	(Brane)
$P\equiv _{b}P'{\mbox{and }}P'\rightarrow _{b}Q'{\mbox{and }}Q'\equiv _{b}Q{\mbox{implies }}P\rightarrow _{b}Q$	$\qquad \qquad$	(Struct)

The action $pino(\rho )$ creates an empty bubble within the membrane where the $pino$ action resides; imagine that the original membrane buckles towards inside and pinches off. The patch $\sigma$ on the empty bubble is a parameter of $pino$. The exo action $n^{\nwarrow }$, which comes with a complementary co-action ${\overline {n}}^{\nwarrow }$, models the merging of two nested membranes, which starts with the membranes touching at a point. In the process (which is a smooth, continuous process), the subsystem $P$ gets expelled to the outside, and all the residual patches of the two membranes become contiguous. The phago action $n^{\searrow }$, which also comes with a complementary co-action ${\overline {n}}^{\searrow }(\rho )$, models a membrane (the one with $Q$) "eating" another membrane (the one with $P$). Again, the process has to be smooth and continuous, so it is biologically implementable. It proceeds by the $Q$ membrane wrapping around the $P$ membrane and joining itself on the other side. Hence, an additional layer of membrane is created around the eaten membrane: the patch on that membrane is specified by the parameter $\rho$ of the co-phago action (similar to the parameter of the pino action).

A translation from the set ${\mathcal {P}}$ of brane processes to the set ${\mathcal {M}}$ of membrane configurations is given formally as follows:

Definition A translation ${\mathcal {T}}:{\mathcal {P}}\rightarrow {\mathcal {M}}$ is given by

${\mathcal {T}}(P)=$ ${\begin{cases}\;[~]_{{\mathcal {S}}(\sigma )}&{\mbox{if }}P=\sigma (~)\\\;[{\mathcal {T}}(R)]_{{\mathcal {S}}(\sigma )}&{\mbox{if }}P=\sigma (R)\\{\mathcal {T}}(Q)\;\|\;{\mathcal {T}}(R)&{\mbox{if }}P=Q\,\mid \,R\\\end{cases}}$

where ${\mathcal {S}}:{\mathcal {P}}\rightarrow V^{*}$ is defined as:

${\mathcal {S}}(\sigma )=$ ${\begin{cases}\sigma &{\mbox{if }}\sigma =n^{\searrow }or\sigma =n^{\nwarrow }or\sigma ={\overline {n}}^{\nwarrow }\\{\overline {n}}^{\searrow }\;\|\;S(\rho )&{\mbox{if }}\sigma ={\overline {n}}^{\searrow }(\rho )\\pino\;\|\;S(\rho )&{\mbox{if }}\sigma =pino(\rho )\\{\mathcal {S}}(a)\;\|\;{\mathcal {S}}(\rho )&{\mbox{if }}\sigma =a.\rho \\{\mathcal {S}}(\tau )\;\|\;{\mathcal {S}}(\rho )&{\mbox{if }}\sigma =\tau \,\mid \,\rho \\\lambda &{\mbox{if }}\sigma =0\end{cases}}$

The rules of the systems of mutual membranes with objects on surface (MMOS) are presented in what follows.

Pino/Exo/Phago Rules of MMOS

---

Pino	$\qquad \qquad$	$[M]_{S(pino(\rho ).\sigma \mid \sigma _{0})}\rightarrow [[~]_{S(\rho )}\;\|\;M]_{S(\sigma \mid \sigma _{0})}$
Exo	$\qquad \qquad$	$[[M]_{S(n^{\nwarrow }.\sigma \mid \sigma _{0})}\;\|\;N]_{S({\overline {n}}^{\nwarrow }.\tau \mid \tau _{0})}\rightarrow M\;\|\;[N]_{S(\sigma \mid \sigma _{0}\mid \tau \mid \tau _{0})}$
Phago	$\qquad \qquad$	$[M_{1}]_{S(n^{\searrow }.\sigma \mid \sigma _{0})}\;\|\;[N]_{S({\overline {n}}^{\searrow }(\rho ).\tau \mid \tau _{0})}\rightarrow [[[M_{1}]_{S(\sigma \mid \sigma _{0})}]_{S(\rho )}\;\|\;N]_{S(\tau \mid \tau _{0})}$

where $M_{1}$ is a multiset and $M$, $N$ are arbitrary membrane configurations.

The next result claims that two PEP systems which are structurally equivalent are translated into systems of mutual membranes with objects on surface which are structurally equivalent.

Proposition. If $P$ is a PEP system and $M={\mathcal {T}}(P)$ is a system of mutual membranes with objects on surface, then there exists $N$ such that $M\equiv _{m}N$ and $N={\mathcal {T}}(Q)$, whenever $P\equiv _{b}Q$.

Proposition. If $P$ is a PEP system and $M={\mathcal {T}}(P)$ is a system of mutual membranes with objects on surface, then there exists $Q$ such that $N={\mathcal {T}}(Q)$ whenever $M\equiv _{m}N$.

Remark. In the last proposition it is possible that $P\not \equiv _{b}Q$. Suppose $P=n^{\searrow }.n^{\nwarrow }(~)$. By translation it is obtained that $M={\mathcal {T}}=[~]_{n^{\searrow }\;\|\;n^{\nwarrow }}\equiv _{m}[~]_{n^{\nwarrow }\;\|\;n^{\searrow }}=N$. It is possible to have $Q=n^{\nwarrow }.n^{\searrow }(~)$ or $Q=n^{\nwarrow }\mid n^{\searrow }(~)$ such that $N={\mathcal {T}}(Q)$, but $P\not \equiv _{b}Q$.

Proposition. If $P$ is a PEP system and $M={\mathcal {T}}(P)$ is a system of mutual membranes with objects on surface, then there exists $N$ such that $M\rightarrow N$ and $N={\mathcal {T}}(Q)$, whenever $P\rightarrow _{b}Q$.

Proposition. If $P$ is a PEP system and $M={\mathcal {T}}(P)$ is a system of mutual membranes with objects on surface, then there exists $Q$ such that $N={\mathcal {T}}(Q)$ whenever $M\rightarrow N$.

The following remark is a consequence of the fact that a formalism using an interleaving semantic is translated into a formalism working in parallel.

Remark. The last proposition allows $P\not \rightarrow _{b}Q$. Let us assume $P={\overline {n}}^{\nwarrow }.{\overline {n}}^{\nwarrow }(n^{\nwarrow }.n^{\searrow }(~))$. By translation, it is obtained that $M=((~)_{n^{\nwarrow }\;\|\;n^{\searrow }})_{{\overline {n}}^{\nwarrow }\;\|\;{\overline {n}}^{\nwarrow }}$, such that $M\rightarrow [~]_{n^{\searrow }\;\|\;{\overline {n}}^{\nwarrow }}$. It can be observed that there exist $Q=n^{\searrow }.{\overline {n}}^{\nwarrow }(~)$ such that $N={\mathcal {T}}(Q)$, but $P\not \rightarrow _{b}Q$.

These results are presented together with their proofs in [2].

References

1. B. Aman, G.Ciobanu. Describing the Immune System Using Enhanced Mobile Membranes. Electr. Notes in Theoretical Computer Science, vol.194(3), 5–18, 2008.
2. B. Aman, G.Ciobanu. Membrane Systems with Surface Objects. Proc. of the International Workshop on Computing with Biomolecules (CBM 2008), 17–29, 2008.
3. B. Aman, G.Ciobanu. Resource Competition and Synchronization in Membranes. Proceedings of SYNASC08, IEEE Computing Society, 145–151, 2009.
4. B. Aman, G.Ciobanu. Simple, Enhanced and Mutual Mobile Membranes. Transactions on Computational Systems Biology XI', LNBI vol.5750, 26–44, 2009.
5. B. Aman, G.Ciobanu. Translating Mobile Ambients into P Systems. Electr. Notes in Theoretical Computer Science, vol.171(2), 11–23, 2007.
6. B. Aman, G.Ciobanu. Turing Completeness Using Three Mobile Membranes. Lecture Notes in Computer Science, vol.5715, 42–55, 2009.
7. B. Aman, G. Ciobanu. On the Relationship Between Membranes and Ambients. Biosystems, vol.91(3), 515–530, 2008.
8. N. Busi. On the Computational Power of the Mate/Bud/Drip Brane Calculus: Interleaving vs. Maximal Parallelism. Lecture Notes in Computer Science, vol.3850, Springer, 144–158, 2006.
9. N. Busi, R. Gorrieri. On the computational power of Brane calculi. Third Workshop on Computational Methods in Systems Biology, 106–117, 2005.
10. L. Cardelli. Brane Calculi. Interactions of biological membranes. Lecture Notes in BioInformatics, vol.3082, 257–278, Springer, 2004.
11. L. Cardelli, A. Gordon. Mobile Ambients. Lecture Notes in Computer Science, vol.1378, Springer, 140–155, 1998.
12. L. Cardelli, Gh. Păun. A universality result for a (mem)brane calculus based on mate/drip operations. Intern. J. Foundations of Computer Science, vol.17(1), 49–68, 2006.
13. L. Cardelli, S. Pradalier. Where Membranes Meet Complexes. BioConcur, 2005.
14. M. Cavaliere, S. Sedwards. Membrane Systems with Peripheral Proteins: Transport and Evolution. Electr. Notes in Theoretical Computer Science, vol.171(2), 37–53, 2007.
15. G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez. Application of Membrane Computing. Springer, 2006.
16. J. Dassow, Gh. Păun. Regulated Rewriting in Formal Language Theory. Springer-Verlag, 1990.
17. S.N. Krishna. The Power of Mobility: Four Membranes Suffice. Lecture Notes in Computer Science, vol.3526, 242–251, Springer, 2005.
18. S.N. Krishna. Membrane computing with transport and embedded proteins. Theoretical Computer Science, vol.410, 355–375, 2009.
19. S.N. Krishna. Universality results for P systems based on brane calculi operations. Theoretical Computer Science, vol.371, 83–105, 2007.
20. S.N. Krishna, G. Ciobanu. On the Computational Power of Enhanced Mobile Membranes. Lecture Notes in Computer Science, vol.5028, 326–335, 2008.
21. S.N. Krishna, Gh. Păun. P Systems with Mobile Membranes. Natural Computing, vol.4(3), 255–274, 2005.
22. F. Levi, D. Sangiorgi. Controlling Interference in Ambients. Proceedings POPL'00, ACM Press, 352–364, 2000.
23. F. Levi, D. Sangiorgi. Mobile Safe Ambients. ACM TOPLAS, vol.25, 1-69, 2003.
24. Gh. Păun. Membrane Computing. An Introduction. Springer-Verlang, Berlin, 2002.
25. Gh. Păun. Membrane Computing and Brane Calculi(Some Personal Notes). Electr. Notes in Theoretical Computer Science, vol.171, 3–10, 2007.