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 ; some applications of the membrane systems are presented in . 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  and brane  calculi . 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: 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 formula_1. The mobility is provided by consumption and rewriting of objects. In terms of computation, the work is performed using membrane configurations. A the set formula_2 of membrane configurations (ranged by formula_3) os defined by using  the free monoid formula_4 (ranged over by formula_5) generated by a finite alphabet formula_6 (ranged over by formula_7): formula_8 If formula_9 and formula_10 are two membrane configurations, formula_9 reduces to formula_10 (denoted by formula_13) if there exists a rule in the set of rules formula_1 applicable to the configuration formula_9 such that the new configuration formula_10 is obtained. When applying the rules of formula_1, also the following inference rules are used: formula_18; formula_19 When describing a computation of a systems of mobile membranes, an initial configuration formula_20 and a set of rules formula_1 are given. The rules used in this  paper describe an formula_22 (object rewriting), formula_23 movement (moving an elementary membrane inside a neighbouring membrane), formula_24 movement (moving an elementary membrane outside the membrane where it is placed), formula_25 (engulfing zero external membranes), and formula_26 (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 formula_27, 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 formula_1 defined as follows: formula_29, for formula_30, formula_31, formula_32; (local object evolution) formula_33, for formula_34, formula_35, formula_32; (global object evolution) formula_37 , for formula_38, formula_39; (endocytosis) formula_40, for formula_38, formula_39; (exocytosis) where formula_43 is a multiset, and formula_9, formula_10 are arbitrary membrane configurations. Turing completeness can be obtained by using nine membranes together with the operations of endocytosis and exocytosis #References|[21 ]. In #References|[17 ] it is proven that four mobile membranes are enough to get the power of a Turing machine, while in #References|[4 ] the number of membranes is decreased to three. formula_46 denotes the family of all sets generated inside a given membrane by simple mobile membranes using local evolution rules (formula_47), endocytosis and exocytosis rules. Whenever global evolution rules (formula_48) are  used, the parameter formula_47 is replaced by formula_48. 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 formula_51 denotes the family of sets of vectors of natural numbers computed by using at most $n$ membranes. formula_52 denoted the family of Turing computable sets of vectors generated by arbitrary grammars. It is proved in #References|[17 ] that formula_53. 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 #References|[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. formula_54. The proof of this result uses a similar technique to that used in #References|[4 ]. Enhanced Mobile Membranes. The "systems of enhanced mobile membranes" are a variant of simple membrane systems proposed in #References|[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 formula_1 defined as follows: formula_56 for formula_57; (endocytosis) formula_58, for formula_59; (exocytosis) formula_60 for formula_61, formula_62; (enhanced endocytosis) formula_63 for formula_64;(enhanced exocytosis) \noindent where formula_9 is a multiset and formula_10 is an arbitrary membrane configuration. The computational power of the systems of enhanced mobile membranes using these four operations was studied in #References|[20 ] where it is proved that twelve membranes can provide the computational universality, while in  #References|[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 #References|[20 ]. The family of all sets generated inside a given membrane by enhanced mobile membranes of degree at most formula_67 using rules formula_68, is denoted by  formula_69. Theorem. formula_70. Theorem. formula_71. 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. formula_72. The proof is similar to that presented in #References|[4 ]. Mutual Mobile Membranes. Following the approach presented in #References|[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 formula_73 and formula_74 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 formula_1 defined as follows: formula_76 for formula_77; (mutual endocytosis) formula_78 for formula_79; (mutual exocytosis) where formula_9 is a multiset and formula_10 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 #References|[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 formula_67 using mutual endocytosis rules ("mendo") and mutual exocytosis rules ("mexo") is denoted by formula_83. Therefore, the result can be formulated as  following. Theorem. formula_84. 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 #References|[20 ]. Mutual Membranes with Objects on Surface. Membrane systems #References|[24 ] and brane calculus #References|[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 #References|[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 #References|[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 #References|[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 formula_1 defined as follows: formula_86, for formula_87 (pino) formula_88, for aformula_89 (exo) formula_90, for formula_91 (phago) \noindent where formula_43 is a multiset and formula_9, formula_10 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 #References|[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: 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 formula_67 membranes, and any of the rules formula_96 of weight at most formula_97 respectively, is denoted by formula_98). When one of the parameters is not bounded, it is replaced it with a formula_99. It is proven in #References|[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. formula_100, for all formula_101. It is proven  in #References|[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. formula_102, for all formula_103. 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 #References|[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 #References|[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 #References|[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 #References|[22,23 ]. Given an infinite set of names formula_104 (ranged over by formula_105), the set formula_106 of SA-processes (denoted by formula_107) together with their capabilities (denoted by formula_108) are defined as follows: formula_109  formula_110 Process formula_111 is an inactive mobile ambient. A movement formula_112 is provided by the capability formula_113, followed by the execution of formula_114. An ambient formula_115 represents a bounded place labelled by formula_67 in which a SA-process formula_114 is executed. formula_118 is a parallel composition of mobile ambients formula_114 and formula_120. formula_121 creates a new unique name formula_67 within the scope of formula_114. The "structural congruence" formula_124 over ambients is the least congruence such that formula_125 is a commutative monoid. The operational semantics of pure ambient safe calculus are defined in terms of a reduction relation formula_126 by the  following axioms and rules. Axioms: formula_127; formula_128; formula_129. Rules: formula_130; formula_131. formula_132 denotes a reflexive and transitive closure of the binary relation formula_126. A translation from the set formula_134 of safe ambients to the set formula_27 of membrane configurations is given formally as follows: Definition. A translation formula_136 is given by formula_137, where formula_138 is formula_139formula_140 An object formula_141 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: formula_142 iff formula_143. Considering two membrane systems formula_9 and formula_10 with only one object formula_141, formula_147 if there is a sequence of rules formula_148, from the particular set of rules used in #References|[7 ], such that applying the rules from this set to the membrane configuration formula_9 it is obtained the membrane configuration formula_10. Proposition. If formula_114 and formula_120 are two ambients and formula_9 is a membrane system such that formula_154 and formula_155, then there exists a set of rules applicable to formula_9 such that formula_147, and formula_158. Proposition. Let formula_9 and  formula_10 be two membrane systems with only one formula_141 object, and an ambient formula_114 such that formula_155. If there is a set of rules applicable to formula_9 such that formula_165, then there exists an ambient formula_120 with formula_167 and formula_158. 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)" 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 #References|[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 #References|[8,9,14,18,19 ]. As it is expressed in #References|[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 #References|[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  #References|[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 #References|[10 ]. Membranes are formed of patches, where a patch formula_175 can be composed from other patches formula_176. An elementary patch formula_175 consists of an action formula_73 followed, after the consumption of it, by another patch formula_179. Actions often come in complementary pairs which cause  the interaction between membranes. The names formula_67 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 #References|[10 ]. The replicator operator is not used because a membrane system cannot be defined without knowing exactly the initial membrane structure. formula_181 denotes the set of brane systems defined above. Some abbreviations can be made: formula_182 as formula_73, formula_184 as formula_185, and formula_186 as formula_187. The structural congruence relation is a way of  rearranging the system such that the interacting parts come together, as illustrated in what follows: In what follows the reduction rules of the calculus are presented: The action formula_188 creates an empty bubble within the membrane where the formula_189 action resides; imagine that the original membrane buckles towards inside and pinches off. The patch formula_190 on the empty bubble is a parameter of formula_189. The exo action formula_192, which comes with a complementary co-action formula_193, 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 formula_194 gets expelled to the outside, and all the residual patches of the two membranes become contiguous. The phago action formula_195, which also comes with a complementary co-action formula_196, models a membrane (the one with formula_197) "eating" another membrane (the one with formula_194). Again, the process has to be smooth and continuous, so it is biologically implementable. It proceeds by the formula_197 membrane wrapping around the formula_194 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 formula_201 of the co-phago action (similar to the parameter of the pino action). A translation from the set formula_181 of brane processes to the set formula_27 of membrane configurations is given formally as follows: Definition A translation formula_204 is given by formula_205 formula_206 where formula_207 is defined as: formula_208 formula_209 The rules of the systems of mutual membranes with objects on surface (MMOS) are presented in what follows. where formula_43 is a multiset and formula_9, formula_10 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 formula_194 is a PEP system and formula_214 is a system of mutual membranes with objects on surface, then there exists formula_10 such that formula_216 and formula_217, whenever formula_218. Proposition. If formula_194 is a PEP system and formula_214 is a system of mutual membranes with objects on surface, then there exists formula_197 such that formula_217 whenever formula_216. Remark. In the last proposition it is possible that formula_224. Suppose formula_225. By translation it is obtained that formula_226. It is possible to have formula_227 or formula_228 such that formula_217, but formula_230. Proposition . If formula_194 is a PEP system and formula_214 is a system of mutual membranes with objects on surface, then there exists formula_10 such that formula_13 and formula_217, whenever formula_236. Proposition. If formula_194 is a PEP system and formula_214 is a system of mutual membranes with objects on surface, then there exists formula_197 such that formula_217 whenever formula_13. 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 formula_242. Let us assume formula_243. By translation, it is obtained that formula_244, such that  formula_245. It can be observed that there exist formula_246 such that formula_217, but formula_248. These results are presented together with their proofs in #References|[2 ]. References. Category:Cell biology