Computational Aspects of Mobile Membranes, Brane Calculi and Mobile Ambients
| Bogdan Aman and Gabriel Ciobanu (2010), Scholarpedia, 5(7):9420. | doi:10.4249/scholarpedia.9420 | revision #91144 [link to/cite this article] |
Prof. Gabriel Ciobanu accepted the invitation on 20 May 2009 (self-imposed deadline: 20 November 2009).
Computational Aspects of Mobile Membranes and Relationships with Brane Calculi and Mobile Ambients is part of the Molecular Computing chapter of Scholarpedia describing various formalisms based on mobile membranes and their relationship to Mobile Ambients and Brane Calculi.
Contents |
Safe Ambients
Safe ambients represent a variant of mobile ambients [9] 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 bellow; more information can be found in [17,18]. 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 A \quad \mid \quad C.A \quad \mid \quad n[\;A\;]\)
\(C\) are called capabilities or actions, and processes \(n[A]\) are called ambients. 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. Each ambient contains a collection of processes, that reside and run directly within it. Ambients can be nested within other ambients. An ambient moves as a whole, with its component processes and sub-ambients. The processes inside an ambient control it, by instructing it to move. \(A\,\mid\,B\) is a parallel composition of mobile ambients\(A\) and \(B\ .\) 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:
\((Comp)\quad\frac{\displaystyle A \Rightarrow_{amb} A'} {\displaystyle A \mid B \Rightarrow_{amb} A' \mid B};\qquad\qquad(Amb)\quad\frac{\displaystyle A \Rightarrow_{amb} A'} {\displaystyle n[\;A\;] \Rightarrow_{amb}n[\;A'\;]};\)\(\qquad\qquad(Struc)\quad\frac{\displaystyle A\equiv_{amb} A', \ A' \Rightarrow_{amb} B', \ B' \equiv_{amb} B}{\displaystyle A \Rightarrow_{amb} B}\ .\)
\(\Rightarrow^*_{amb}\) denotes a reflexive and transitive closure of the binary relation \(\Rightarrow_{amb}\ .\)
Ambient calculus was extended to BioAmbients [21] in order to allow the study of biological compartments of different granularities, movement of molecules between compartments, and dynamic rearrangement of cellular compartments and molecular complexes.
Brane Calculi
Brane calculi [8] represent a family of process calculi proposed for modeling the behavior of biological membranes. Brane calculi represent an evolution of BioAmbients, the main difference consisting in the fact that brane calculi deal with membranes representing the sites of activity; thus a computation happens on the membrane surface. Two basic brane calculi are defined by the following operations pino, exo, phago (PEP) and mate, drip, bud (MBD) inspired by biologic processes as endocytosis, exocytosis and mitosis. An encoding of the MBD primitives into PEP primitives is provided in [8]. The set of brane systems (denoted by \(P,P',Q,Q',\dots\)) together with their branes (denoted by \(\tau,\tau',\sigma,\sigma',\rho,\rho',\dots\)) and their actions (denoted by \(a,a',b,b',\ldots\)) are defined as follows:
| Systems | \(P\) | \(::\,=\) | \(P \circ P \;\mid\;\sigma(~)\;\mid\;\sigma(P)\) | nests of membranes |
|---|---|---|---|---|
| Branes | \(\sigma\) | \(::\,=\) | \(0\;\mid\;\sigma\mid\sigma \;\mid\; a.\sigma\) | combinations of actions |
| Actions | \(a\) | \(::\,=\) | \(n^{\searrow}\;\mid\;\overline{n}^{\searrow}(\sigma)\;\mid\; n^{\nwarrow}\;\mid\;\overline{n}^{\nwarrow}\;\mid\;pino (\sigma)\) | phago \(\searrow\ ,\) exo \(\nwarrow\) |
\(\mathcal{P}\) denotes the set of brane systems defined above and \(\mathcal{B}\) denotes the set of branes. Actions often come in complementary pairs which cause the interaction between membranes. The names \(n\) are used to pair-up actions and co-actions. We use some abbreviations\[a.0\] as \(a\ ,\) \(0(P)\) as \((P)\ ,\) and \(0(~)\) as \((~)\ .\) Moreover, \(a.\sigma|\tau\) stands for \((a.\sigma)|\tau\ .\)
According to Cardelli [8], the structural congruence is applied to systems and branes in order to characterize their fluidity properties:
| \(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 PEP calculus are presented:
| \(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 in and then 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 then joining back onto 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).
Projective brane calculus [12] represent a refinement of brane calculus in which the membrane actions are directed; this modification brings the language closer to biological membranes.
Mobile Membranes
Mobile membranes represent a formalism describing the movement of membranes inside a spatial structure by applying rules from a given set. Mobile membranes represent a variant of membrane computing [19]. The model is characterized by two essential features:
- A spatial structure consisting of a hierarchy of membranes (which do not intersect). The membranes produce a delimitation between regions. For each membrane there is a unique associated region. To each membrane we associate a multiset of objects placed on its surface and a multiset of objects placed inside the corresponding region. A membrane without any other membranes inside is called elementary, while a membrane containing other membranes is called composite.
- 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 (creating an elementary membrane) and phagocytosis (engulfing just one sibling elementary membrane). A movement rule consists in fact in two steps: rewriting the objects that initiated the movement to multisets of objects and changing the membrane structure.
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 we apply a maximal multiset of rules, 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.
In terms of computation, we are working with membrane configurations. We define the set \({\mathcal M}\) of membrane configurations (ranged by \(M,N,\dots\)) by using the free monoid \(V^*\) (ranged over by \(u,v,\dots\) with \(\lambda\) denoting the empty word) generated by a finite alphabet \(V\) of objects (ranged over by \(a,b,\dots\))\[\quad M::= u \;\mid\; [\;M\;]_u\;\mid\;M \; M\]
If \(M\) and \(N\) are two membrane configurations, we say that \(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 we can obtain the new configuration \(N\ .\) We can also apply the following inference rules\[\qquad(Par) \quad \frac{\displaystyle M \ \rightarrow \ M'\qquad\displaystyle N \ \rightarrow \ N'} {\displaystyle M\;N \ \rightarrow \ M'\;N'}\qquad\qquad(Mem) \ \frac{\displaystyle M \ \rightarrow \ M'} {\displaystyle [\;M\;]_u \rightarrow [\;M'\;]_u};\] \(\qquad \qquad (Struct) \ \frac{\displaystyle M\equiv_{mem} M'\quad M' \rightarrow N'\quad \ N' \equiv_{mem} N} {\displaystyle M \rightarrow N}\ ,\)
where \( \equiv_{mem}\) represents a structural congruence defined as follows\[M\equiv_{mem}M\quad\qquad M\;N \equiv_{mem} N\;M\quad\qquad M\;(N\;M')\equiv_{mem}(M\;N)\;M'\qquad\quad M\;\lambda \equiv_{mem} M\]
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 we define four classes of mobile membranes inspired from biological facts, and show that their computational power depends on their initial configuration and set of rules.
Simple Mobile Membranes
The systems of simple mobile membranes (SM) are defined over the set of configurations \(\mathcal{M}\ .\) The evolution from a configuration to another is given by the following rules\[(Local~Object~Evolution) \qquad \! [[a\;M]_c\;N]_d \rightarrow [[v\;M]_c\;N]_d\ ,\] where \(a,c,d \in V\ ,\) \(v \in V^*\ ;\) \(~{\color{white}.}\)250px
\((Global~Object~Evolution) \quad[a\;M]_c \rightarrow [v\;M]_c\ ,\) where \(a,c\in V\ ,\) \(v \in V^*\ ;\)
\(~~~~~~~~~~~~~~~~~~{\color{white}.}\)
\((Endocytosis)\qquad\qquad\qquad \ \ [a\;u]_d\;[M]_c \rightarrow [[b\;u]_d\;M]_c\ ,\) where \(a,b,c,d \in V\ ,\) \(u \in V^*\ ;\)
\({\color{white}.}\)
\((Exocytosis)\qquad\qquad\qquad\quad[[a\;u]_d\;M]_c \rightarrow [b\;u]_d\;[M]_c\ ,\) where \(a,b,c,d \in V\ ,\) \(u \in V^*\ .\)
\(~{\color{white}.}\)
In [16] Turing completeness can be obtained by using nine membranes together with the operations of endocytosis and exocytosis. In [13] it is proved that four mobile membranes are enough to get the power of a Turing machine, while in [3] we decreased the number of membranes to three.
\(SM_n(levol,endo,exo)\) denotes the family of sets of vectors of natural numbers, counting the objects from all membranes, computed by using at most \(n\) membranes and local evolution rule (\(levol\)), endocytosis rule (\(endo\)) and exocytosis rule (\(exo\)). 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. We denote by \(RE\) the family of Turing computable sets of vectors generated by arbitrary grammars.
It is proved in [13] that \(SM_4(gevol,endo,exo)=RE\ .\) We follow the research line initiated in membrane computing 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 we improve previous result presented in [13] 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 technique similar to that presented in [3].
Enhanced Mobile Membranes
Following our approach presented in [1], we define systems of enhanced mobile membranes (EM) over the set of configurations \(\mathcal{M}\) as a variant of systems of simple mobile membranes. The evolution from a configuration to another is given by the following rules\[(Endocytosis)\qquad\qquad\qquad \ \![a\;u]_d\;[M]_c \rightarrow [[b\;u]_d\;M]_c\ ,\] where \(a,b,c,d \in V\ ,\) \(u \in V^*\ ;\)
\(~~~{\color{white}.}\)
\((Exocytosis)\qquad\qquad\qquad \ \ \! [[a\;u]_d\;M]_c \rightarrow [b\;u]_d\;[M]_c\ ,\) where \(a,b,c,d \in V\ ,\) \(u \in V^*\ ;\)
\(~~~~{\color{white}.}\)
\((Enhanced~Endocytosis)\qquad \![u]_d\;[a\;M]_c \rightarrow [[u]_d\;b\;M]_c\ ,\) where \(a,b,c,d \in V\ ,\) \(u \in V^*\ ;\)
\(~~{\color{white}.}\)
\((Enhanced~Exocytosis)\qquad \ [[u]_d\;a\;M]_c \rightarrow [u]_d\;[b\;M]_c\ ,\) where \(a,b,c,d \in V\ ,\) \(u \in V^*\ .\)
\(~~{\color{white}.}\)
The computational power of the systems of enhanced mobile membranes using these four operations was studied in [15] where it is proved that twelve membranes can provide the computational universality, while in [3] we improved the result by reducing the number of membranes to nine.
\(EM_n(\alpha)\) denotes the family of sets of vectors of natural numbers, counting the objects from all membranes, computed by using at most \(n\) membranes and endocytosis (endo), exocytosis (exo), enhanced endocytosis (fendo), enhanced exocytosis (fexo) rules, where \(\alpha \subseteq \{exo, endo, fendo, fexo\}\ .\)
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. In what follows we have proven that using the same types of rules (endo, exo, fendo, fexo) we can construct a membrane system 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 of this result uses a technique similar to that presented in [3].
Mutual Mobile Membranes
We define systems of mutual mobile membranes (MM) 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; this agreement is described by using dual objects \(a\) and \(\overline{a}\) in the involved membranes. The evolution from a configuration to another is given by the following rules\[(Mutual~Endocytosis)\qquad\!
[a\;v]_d \;[\overline{a}\;v'\;M]_c \rightarrow [\;[w]_d \;w'\;M]_c\] for \(a, \overline{a},c,d\in V, v,v',w,w' \!\! \in V^*\ ;\)
\((Mutual~Exocytosis)\qquad \ [\;[a\;v]_d\;\overline{a}\;v'\;M]_c \rightarrow [w]_d \;[w'\;M]_c\) for \(a, \overline{a},c,d\in V, v,v',w,w'\!\! \in V^*\ .\)
In [5] we prove that Turing completeness can be obtained by using three membranes together with the operations of mutual endocytosis and mutual exocytosis. Three also represents the minimum number of membranes in order to discuss properly about the movement provided by endocytosis and exocytosis: we work with configurations corresponding to a system of two membranes moving inside a skin membrane.
\(MM_n(mendo,mexo)\) denotes the family of sets of vectors of natural numbers, counting the objects from all membranes, computed by using at most \(n\) membranes and mutual endocytosis rules (mendo) and mutual exocytosis rules (mexo).
Theorem. \(MM_{3}(mendo,mexo)=RE\ .\)
The proof of this result uses a technique similar to that presented for systems of enhanced mobile membranes in [15].
Mutual Membranes with Objects on Surface
In [2] we defined systems of mutual membranes with objects on surface (MMOS), following the ideas from [10,14] where objects are added on the surface of membranes and the biologically inspired rules pino/exo/phago are used. We use objects and co-objects 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 given by the following rules\[(Pino)\qquad \ [M]_{v\;a\;u} \rightarrow [[~]_{u\;x}\;M]_{v\;y}\ ,\] for \(a \in V, u,v,x,y \in V^*, ux,vy \in V^+\ ;\)
\(~~~~~~~~~~~~~~~~~~~~\;{\color{white}.}\)
\((Exo)\qquad \ \ [[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^+\ ;\)
\(~~~~~~~~~~~~~~~~~~~{\color{white}.}\)
\((Phago)\qquad \! \! [w]_{a\;u} \;[N]_{\overline{a}\;b\;v} \rightarrow [[[w]_{u\;x}]_b\;N]_{v\;y}\ ,\) for \(a,\overline{a},b\! \in\! V, u,v,w,x,y \in V^*, ux,vy \in V^+\ .\)
\(~~~{\color{white}.}\)
The family of sets of vectors of natural numbers, counting the objects from all membranes, is considered as a result of the computation. 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)\)).
In [14] Turing completeness can be obtained by using eight membranes together with the operations of pino and exo operations of weight four and three. We show that we can obtain Turing completeness with only three membranes by increasing the weight of the pino and exo operations with one.
Theorem. \(MMOS_m(pino(r),exo(s)) = RE\ ,\) for all \(m \geq 3, r \geq 5, s \geq 4\ .\)
In [14] Turing completeness can be obtained by using nine membranes together with the operations of phago and exo operations of weight four and three (or five and two). We show that we can obtain Turing completeness with only four membranes by increasing the weight of the phago and exo operations from four and three (or five and two) to six and three.
Theorem. \(MMOS_m(phago(r),exo(s)) = RE\ ,\) for all \(m \geq 4, r \geq 6, s \geq 3\ .\)
A summary of the results is given in what follows:
| Operations | \(\qquad\)Number of membranes | \(\qquad\)Weight | \(\qquad\)RE | \(\qquad\)Where |
|---|---|---|---|---|
| \((Pino)\ ,\) \((Exo)\) | \(8\) | \(4\ ,\) \(3\) | Yes | Theorem 6.1 [14] |
| \((Pino)\ ,\) \((Exo)\) | \(3\) | \(5\ ,\) \(4\) | Yes | Here |
| \((Phago)\ ,\) \((Exo)\) | \(9\) | \(5\ ,\) \(2\) | Yes | Theorem 6.2 [13] |
| \((Phago)\ ,\) \((Exo)\) | \(9\) | \(4\ ,\) \(3\) | Yes | Theorem 6.2 [14] |
| \((Phago)\ ,\) \((Exo)\) | \(4\) | \(6\ ,\) \(3\) | Yes | Here |
Biological motivations of the rules and some examples describing biological systems by using various versions of mobile membranes are presented in [2,3].
Embedding Brane Calculi into Mobile Membranes
“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”[20]. By defining an encoding of the PEP fragment of brane calculus into membranes with objects on surface, we show that the difference between the two models is not significant. Another difference regarding the semantics of the two formalisms is expressed in [7]: ”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).”
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\,\circ\,R\\ \end{cases} \)
where \(\mathcal{S}: \mathcal{B} \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 in this case as follows:
| \(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\) | \([w]_{S(n^{\searrow}.\sigma\mid\sigma_0)}\;[N]_{S(\overline{n}^{\searrow}(\rho).\tau\mid\tau_0)} \rightarrow [[[w]_{S(\sigma\mid\sigma_0)}]_{S(\rho)}\;N]_{S(\tau\mid\tau_0)}\) |
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\ .\)
Embedding Mobile Ambients into Mobile Membranes
The mobile membranes and the mobile ambients [9] 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 [8,11]. 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 link between these models (mobile ambients and mobile membranes) is presented in [4,6].
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}_1:\mathcal{A} \rightarrow \mathcal{M}\) is given by \(\mathcal{T}_1(A)=dlock~\mathcal{T}_2(A)\ ,\) where \(\mathcal{T}_2: \mathcal{A} \rightarrow \mathcal{M}\) is
\(\qquad\mathcal{T}_2(A) =\)\(\begin{cases} cap~n\;[~]_{cap~n} & \mbox{if } A=cap~n \mbox{ for } cap\in \{in,out,open\}\\ cap~n\;[\;\mathcal{T}_2(A_1)\;]_{cap~n} & \mbox{if } A=cap~n.\,A_1 \mbox{ for } cap\in \{in,out,open\}\\ \;[\;\mathcal{T}_2(A_1)\;]_n & \mbox{if } A=n[\;A_1\;]\\ \;[~]_n & \mbox{if } A=n[~]\\ \mathcal{T}_2(A_1)\;\mathcal{T}_2(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}_1(A)\equiv_{mem} \mathcal{T}_1(B)\ .\)
Considering two membrane configurations \(M\) and \(N\) containing only one object \(dlock\) and a sequence of rules \(r_1,\ldots,r_i\ ,\) from the particular set of rules used in [6], by applying these rules to the membrane configuration \(M\) we obtain the membrane configuration \(N\) (we denote this evolution by \(M \Rightarrow_{mem} 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}_1(A)\ ,\) then there exists a set of rules applicable to \(M\) such that \(M \Rightarrow_{mem} N\ ,\) and \(N=\mathcal{T}_1(B)\ .\)
Proposition. Let \(M\) and \(N\) be two membrane systems with only one \(dlock\) object, and an ambient \(A\) such that \(M=\mathcal{T}_1(A)\ .\) If there exists 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}_1(B)\ .\) The number of pairs of non-star objects consumed in membrane systems is equal to the number of pairs of capabilities consumed in ambients.
Theorem. (Operational correspondence)
- If \(A \Rightarrow_{amb} B\ ,\) then \(\mathcal{T}_1(A) \Rightarrow_{mem} \mathcal{T}_1(B)\ .\)
- If \(\mathcal{T}_1(A)\Rightarrow_{mem} M\ ,\) then there is \(B\) such that \(A\Rightarrow_{amb} B\) and \(M=\mathcal{T}_1(B)\ .\)
References
1. B. Aman, G.Ciobanu. Describing the Immune System Using Enhanced Mobile Membranes. Electronic Notes in Theoretical Computer Science, vol.194(3), 5-18, 2008.
2. B. Aman, G.Ciobanu. Membrane Systems with Surface Objects. Proceedings of the International Workshop on Computing with Biomolecules (CBM 2008), 17-29, 2008.
3. B. Aman, G.Ciobanu. Simple, Enhanced and Mutual Mobile Membranes. Transactions on Computational Systems Biology XI', LNBI vol.5750, 26-44, 2009.
4. B. Aman, G.Ciobanu. Translating Mobile Ambients into P Systems. Electronic Notes in Theoretical Computer Science, vol.171(2), 11-23, 2007.
5. B. Aman, G.Ciobanu. Turing Completeness Using Three Mobile Membranes. Lecture Notes in Computer Science, vol.5715, 42-55, 2009.
6. B. Aman, G. Ciobanu. On the Relationship Between Membranes and Ambients. Biosystems, vol.91(3), 515-530, 2008.
7. N. Busi. On the Computational Power of the Mate/Bud/Drip Brane Calculus: Interleaving vs. Maximal Parallelism. Lecture Notes in Computer Science, vol.3850, 144-158, 2006.
8. L. Cardelli. Brane Calculi. Interactions of Biological Membranes. Lecture Notes in BioInformatics, vol.3082, 257-278, 2004.
9. L. Cardelli, A. Gordon. Mobile Ambients. Lecture Notes in Computer Science, vol.1378, Springer, 140-155, 1998.
10. L. Cardelli, Gh. Păun. An Universality Result for a (Mem)brane Calculus Based on mate/drip Operations. Int'l Journal of Foundations of Computer Science, vol.17(1), 49-68, 2006.
11. G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez. Application of Membrane Computing. Springer, 2006.
12. V. Danos, S. Pradalier. Projective Brane Calculus. Lecture Notes in Computer Science, vol.3082, 134-148, Springer, 2005.
13. S.N. Krishna. The Power of Mobility: Four Membranes Suffice. Lecture Notes in Computer Science, vol.3526, 242-251, Springer, 2005.
14. S.N. Krishna. Universality Results for P systems Based on Brane Calculi Operations. Theoretical Computer Science, vol.371, 83-105, 2007.
15. S.N. Krishna, G. Ciobanu. On the Computational Power of Enhanced Mobile Membranes. Lecture Notes in Computer Science, vol.5028, 326-335, 2008.
16. S.N. Krishna, Gh. Păun. P Systems with Mobile Membranes. Natural Computing, vol.4(3), 255-274, 2005.
17. F. Levi, D. Sangiorgi. Controlling Interference in Ambients. Proceedings POPL'00, ACM Press, 352-364, 2000.
18. F. Levi, D. Sangiorgi. Mobile Safe Ambients. ACM TOPLAS, vol.25, 1-69, 2003.
19. Gh. Păun. Membrane Computing. An Introduction. Springer-Verlang, Berlin, 2002.
20. Gh. Păun. Membrane Computing and Brane Calculi(Some Personal Notes). Electr. Notes in Theoretical Computer Science, vol.171, 3-10, 2007.
21. A. Regev, E. Panin, W. Silverman, L. Cardelli, E. Shapiro. BioAmbients: an Abstraction for Biological Compartments. Theoretical Computer Science, vol.325(1), 141-167, 2004.
Internal references
- Gheorghe Paun (2010) Membrane Computing. Scholarpedia, 5(1):9259.
- Paul M.B. Vitanyi (2009) Turing machine. Scholarpedia, 4(3):6240.
