Mobile membranes

The systems of simple mobile membranes (SM) are defined over the set of configurations ${\displaystyle {\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 ${\displaystyle R}$ defined as follows:

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

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

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

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

where ${\displaystyle M_{1}}$ is a multiset, and ${\displaystyle M}$, ${\displaystyle 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.

${\displaystyle SM(levol,endo,exo)}$ denotes the family of all sets generated inside a given membrane by simple mobile membranes using local evolution rules (${\displaystyle levol}$), endocytosis and exocytosis rules. Whenever global evolution rules (${\displaystyle gevol}$) are used, the parameter ${\displaystyle levol}$ is replaced by ${\displaystyle 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 ${\displaystyle SM_{n}(gevol,endo,exo)}$ denotes the family of sets of vectors of natural numbers computed by using at most $n$ membranes. ${\displaystyle RE}$ denoted the family of Turing computable sets of vectors generated by arbitrary grammars.

It is proved in [17] that ${\displaystyle 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. ${\displaystyle SM_{3}(levol,endo,exo)=RE}$.

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

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 ${\displaystyle R}$ defined as follows:

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

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

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

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

\noindent where ${\displaystyle M}$ is a multiset and ${\displaystyle 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 ${\displaystyle n}$ using rules ${\displaystyle \alpha \subseteq \{exo,endo,fendo,fexo\}}$, is denoted by ${\displaystyle EM_{n}(\alpha )}$.

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

Theorem. ${\displaystyle 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. ${\displaystyle EM_{9}(endo,exo,fendo,fexo)=RE}$.

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

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 ${\displaystyle a}$ and ${\displaystyle {\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 ${\displaystyle R}$ defined as follows:

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

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

where ${\displaystyle M}$ is a multiset and ${\displaystyle 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 ${\displaystyle n}$ using mutual endocytosis rules (mendo) and mutual exocytosis rules (mexo) is denoted by ${\displaystyle MM_{n}(mendo,mexo)}$. Therefore, the result can be formulated as following.

Theorem. ${\displaystyle 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].

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 ${\displaystyle R}$ defined as follows:

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

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

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

\noindent where ${\displaystyle M_{1}}$ is a multiset and ${\displaystyle M}$, ${\displaystyle 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	${\displaystyle \qquad }$Number of membranes	${\displaystyle \qquad }$Weight	${\displaystyle \qquad }$RE	${\displaystyle \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 ${\displaystyle n}$ membranes, and any of the rules ${\displaystyle r_{1},r_{2}\in \{pino,exo,phago\}}$ of weight at most ${\displaystyle r,s}$ respectively, is denoted by ${\displaystyle MMOS_{n}(r_{1}(r),r_{2}(s)}$). When one of the parameters is not bounded, it is replaced it with a ${\displaystyle *}$.

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. Howevere, 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. ${\displaystyle MMOS_{m}(pino(r),exo(s))=RE}$, for all ${\displaystyle 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. ${\displaystyle MMOS_{m}(phago(r),exo(s))=RE}$, for all ${\displaystyle m\geq 4,r\geq 6,s\geq 3}$.

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 ${\displaystyle {\mathcal {N}}}$ (ranged over by ${\displaystyle m,n,\dots }$), the set ${\displaystyle {\mathcal {A}}}$ of SA-processes (denoted by ${\displaystyle A,A',B,B',\dots }$) together with their capabilities (denoted by ${\displaystyle C,C',\dots }$) are defined as follows:

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

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

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

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

Axioms:

${\displaystyle (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'\;]}$;

${\displaystyle (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'\;]}$;

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

Rules:

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

${\displaystyle (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}}}$.

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

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

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

${\displaystyle \qquad {\mathcal {T}}_{1}(A)=}$${\displaystyle {\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 ${\displaystyle 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: ${\displaystyle \qquad \qquad A\equiv _{amb}B}$ iff ${\displaystyle {\mathcal {T}}(A)\equiv _{mem}{\mathcal {T}}(B)}$.

Considering two membrane systems ${\displaystyle M}$ and ${\displaystyle N}$ with only one object ${\displaystyle dlock}$, ${\displaystyle M\Rightarrow _{mem}N}$ if there is a sequence of rules ${\displaystyle 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 ${\displaystyle M}$ it is obtained the membrane configuration ${\displaystyle N}$.

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

Proposition. Let ${\displaystyle M}$ and ${\displaystyle N}$ be two membrane systems with only one ${\displaystyle dlock}$ object, and an ambient ${\displaystyle A}$ such that ${\displaystyle M={\mathcal {T}}(A)}$. If there is a set of rules applicable to ${\displaystyle M}$ such that ${\displaystyle M\Rightarrow _{mem}N}$, then there exists an ambient ${\displaystyle B}$ with ${\displaystyle A\Rightarrow _{amb}^{*}B}$ and ${\displaystyle 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 ${\displaystyle A\Rightarrow _{amb}B}$, then ${\displaystyle {\mathcal {T}}(A)\Rightarrow _{mem}{\mathcal {T}}(B)}$.
• If ${\displaystyle {\mathcal {T}}(A)\Rightarrow _{mem}M}$, then exists ${\displaystyle B}$ such that ${\displaystyle A\Rightarrow _{amb}B}$ and ${\displaystyle M={\mathcal {T}}(B)}$.

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	${\displaystyle P,Q}$	${\displaystyle$ ::\,=}	${\displaystyle P\circ Q\;\mid \;\sigma (~)\;\mid \;\sigma (P)}$	nests of membranes
Branes	${\displaystyle \sigma ,\tau }$	${\displaystyle$ ::\,=}	${\displaystyle O\;\mid \;\sigma \mid \tau \;\mid \;a.\sigma }$	combinations of actions
Actions	${\displaystyle a,b}$	${\displaystyle$ ::\,=}	${\displaystyle n^{\searrow }\;\mid \;{\overline {n}}^{\searrow }(\sigma )\;\mid \;n^{\nwarrow }\;\mid \;{\overline {n}}^{\nwarrow }\;\mid \;pino(\sigma )}$	phago ${\displaystyle \searrow }$, exo ${\displaystyle \nwarrow }$

Membranes are formed of patches, where a patch ${\displaystyle s}$ can be composed from other patches ${\displaystyle s=s_{1}\;\mid \;s_{2}}$. An elementary patch ${\displaystyle s}$ consists of an action ${\displaystyle a}$ followed, after the consumption of it, by another patch ${\displaystyle s_{1}s=a.s_{1}}$. Actions often come in complementary pairs which cause the interaction between membranes. The names ${\displaystyle 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. ${\displaystyle {\mathcal {P}}}$ denotes the set of brane systems defined above. Some abbreviations can be made: ${\displaystyle a.0}$ as ${\displaystyle a}$, ${\displaystyle 0(P)}$ as ${\displaystyle (P)}$, and ${\displaystyle 0(~)}$ as ${\displaystyle (~)}$.

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

---

${\displaystyle P\circ Q\equiv _{b}Q\circ P}$	${\displaystyle \qquad \qquad }$	${\displaystyle \sigma \;\mid \;\tau \equiv _{b}\tau \;\mid \;\sigma }$
${\displaystyle P\circ (Q\circ R)\equiv _{b}(P\circ Q)\circ R}$	${\displaystyle \qquad \qquad }$	${\displaystyle \sigma \;\mid \;(\tau \;\mid \;\rho )\equiv _{b}(\sigma \;\mid \;\tau )\;\mid \;\rho }$
${\displaystyle \qquad }$	${\displaystyle \qquad \qquad }$	${\displaystyle \sigma \;\mid \;0\equiv _{b}\sigma }$
${\displaystyle \qquad }$	${\displaystyle \qquad \qquad }$	${\displaystyle \qquad }$
${\displaystyle P\equiv _{b}Q{\mbox{implies }}P\circ R\equiv _{b}Q\circ R}$	${\displaystyle \qquad \qquad }$	${\displaystyle \sigma \equiv _{b}\tau {\mbox{implies }}\sigma \;\mid \;\rho \equiv _{b}\tau \;\mid \;\rho }$
${\displaystyle P\equiv _{b}Q{\mbox{and }}\sigma \equiv _{b}\tau {\mbox{implies }}\sigma (P)\equiv _{b}\tau (Q)}$	${\displaystyle \qquad \qquad }$	${\displaystyle \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

---

${\displaystyle pino(\rho ).\sigma \mid \sigma _{0}(P)\rightarrow _{b}\sigma \mid \sigma _{0}(\rho (~)\circ P)}$	${\displaystyle \qquad \qquad }$	(Pino)
${\displaystyle {\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)}$	${\displaystyle \qquad \qquad }$	(Exo)
${\displaystyle 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)}$	${\displaystyle \qquad \qquad }$	(Phago)
${\displaystyle P\rightarrow _{b}Q{\mbox{implies }}P\circ R\rightarrow _{b}Q\circ R}$	${\displaystyle \qquad \qquad }$	(Par)
${\displaystyle P\rightarrow _{b}Q{\mbox{implies }}\sigma (P)\rightarrow _{b}\sigma (Q)}$	${\displaystyle \qquad \qquad }$	(Brane)
${\displaystyle P\equiv _{b}P'{\mbox{and }}P'\rightarrow _{b}Q'{\mbox{and }}Q'\equiv _{b}Q{\mbox{implies }}P\rightarrow _{b}Q}$	${\displaystyle \qquad \qquad }$	(Struct)

The action ${\displaystyle pino(\rho )}$ creates an empty bubble within the membrane where the ${\displaystyle pino}$ action resides; imagine that the original membrane buckles towards inside and pinches off. The patch ${\displaystyle \sigma }$ on the empty bubble is a parameter of ${\displaystyle pino}$. The exo action ${\displaystyle n^{\nwarrow }}$, which comes with a complementary co-action ${\displaystyle {\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 ${\displaystyle P}$ gets expelled to the outside, and all the residual patches of the two membranes become contiguous. The phago action ${\displaystyle n^{\searrow }}$, which also comes with a complementary co-action ${\displaystyle {\overline {n}}^{\searrow }(\rho )}$, models a membrane (the one with ${\displaystyle Q}$) "eating" another membrane (the one with ${\displaystyle P}$). Again, the process has to be smooth and continuous, so it is biologically implementable. It proceeds by the ${\displaystyle Q}$ membrane wrapping around the ${\displaystyle 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 ${\displaystyle \rho }$ of the co-phago action (similar to the parameter of the pino action).

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

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

${\displaystyle {\mathcal {T}}(P)=}$ ${\displaystyle {\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 ${\displaystyle {\mathcal {S}}:{\mathcal {P}}\rightarrow V^{*}}$ is defined as:

${\displaystyle {\mathcal {S}}(\sigma )=}$ ${\displaystyle {\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	${\displaystyle \qquad \qquad }$	${\displaystyle [M]_{S(pino(\rho ).\sigma \mid \sigma _{0})}\rightarrow [[~]_{S(\rho )}\;\|\;M]_{S(\sigma \mid \sigma _{0})}}$
Exo	${\displaystyle \qquad \qquad }$	${\displaystyle [[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	${\displaystyle \qquad \qquad }$	${\displaystyle [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 ${\displaystyle M_{1}}$ is a multiset and ${\displaystyle M}$, ${\displaystyle 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 ${\displaystyle P}$ is a PEP system and ${\displaystyle M={\mathcal {T}}(P)}$ is a system of mutual membranes with objects on surface, then there exists ${\displaystyle N}$ such that ${\displaystyle M\equiv _{m}N}$ and ${\displaystyle N={\mathcal {T}}(Q)}$, whenever ${\displaystyle P\equiv _{b}Q}$.

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

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

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

Proposition. If ${\displaystyle P}$ is a PEP system and ${\displaystyle M={\mathcal {T}}(P)}$ is a system of mutual membranes with objects on surface, then there exists ${\displaystyle Q}$ such that ${\displaystyle N={\mathcal {T}}(Q)}$ whenever ${\displaystyle 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 ${\displaystyle P\not \rightarrow _{b}Q}$. Let us assume ${\displaystyle P={\overline {n}}^{\nwarrow }.{\overline {n}}^{\nwarrow }(n^{\nwarrow }.n^{\searrow }(~))}$. By translation, it is obtained that ${\displaystyle M=((~)_{n^{\nwarrow }\;\|\;n^{\searrow }})_{{\overline {n}}^{\nwarrow }\;\|\;{\overline {n}}^{\nwarrow }}}$, such that ${\displaystyle M\rightarrow [~]_{n^{\searrow }\;\|\;{\overline {n}}^{\nwarrow }}}$. It can be observed that there exist ${\displaystyle Q=n^{\searrow }.{\overline {n}}^{\nwarrow }(~)}$ such that ${\displaystyle N={\mathcal {T}}(Q)}$, but ${\displaystyle P\not \rightarrow _{b}Q}$.

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