Mobile membranes
Introduction 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 #References|24; some applications of the membrane systems are presented in #References|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 #References|11 and brane calculi #References|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 . The mobility is provided by consumption and rewriting of objects. In terms of computation, the work is performed using membrane configurations. A the set  of membrane configurations (ranged by ) os defined by using the free monoid  (ranged over by ) generated by a finite alphabet  (ranged over by ):If  and  are two membrane configurations,  reduces to  (denoted by ) if there exists a rule in the set of rules  applicable to the configuration  such that the new configuration  is obtained. When applying the rules of , also the following inference rules are used:;When describing a computation of a systems of mobile membranes, an initial configuration  and a set of rules  are given. The rules used in this paper describe an  (object rewriting),  movement (moving an elementary membrane inside a neighbouring membrane),  movement (moving an elementary membrane outside the membrane where it is placed),  (engulfing zero external membranes), and  (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 , 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  defined as follows:, for , , ; '''(local object evolution)''', for , , ; '''(global object evolution)''', for , ; '''(endocytosis)''', for , ;  '''(exocytosis)'''where  is a multiset, and ,  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. denotes the family of all sets generated inside a given membrane by simple mobile membranes using local evolution rules (), endocytosis and exocytosis rules. Whenever global evolution rules () are used, the parameter  is replaced by . 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  denotes the family of sets of vectors of natural numbers computed by using at most $n$ membranes. denoted the family of Turing computable sets of vectors generated by arbitrary grammars.It is proved in #References|17 that . 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.''' .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 fordescribing some biological mechanisms of the immune system. The operations governing the mobility of the systems of enhanced mobilemembranes are endocytosis (endo), exocytosis (exo), forced endocytosis (fendo), forced exocytosis (fexo).The evolution from aconfiguration to another is made using rules from the set of rules  defined as follows: for ; '''(endocytosis)''', for ; '''(exocytosis)''' for ,; '''(enhanced endocytosis)''' for ;'''(enhanced exocytosis)'''\noindent where  is a multiset and  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  using rules , is denoted by . '''Theorem.''' . '''Theorem.''' .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.''' .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  and  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  defined as follows: for ; '''(mutual endocytosis)''' for ; '''(mutual exocytosis)'''where  is a multiset and  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  using mutual endocytosis rules (''mendo'') and mutual exocytosis rules (''mexo'') is denoted by . Therefore, the result can be formulated as following.'''Theorem.''' .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 mobilemembranes #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  defined as follows:, for  '''(pino)''', for a '''(exo)''', for  '''(phago)'''\noindent where  is a multiset and ,  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:+Summary of Results---- Operations  Number of membranes  Weight  RE  Where Pino, exo  8  4,3  Yes  Theorem 6.1 #References|19 Pino, exo  3  5,4  Yes  Here Phago, exo  9  5,2  Yes  Theorem 6.2 #References|19 Phago, exo  9  4,3  Yes  Theorem 6.2 #References|19 Phago, exo  4  6,3  Yes  HereThe 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 computationat most  membranes, and any of the rules  of weight at most  respectively, is denoted by ). When one of the parameters is not bounded, it is replaced it with a .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.''' , for all .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.''' , for all .
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  (ranged over by ), the set  of SA-processes (denoted by ) together with their capabilities (denoted by ) are defined as follows:Process  is an inactive mobile ambient. A movement  is provided by the capability , followed by the execution of . An ambient  represents a bounded place labelled by  in which a SA-process  is executed. is a parallel composition of mobile ambients  and . creates a new unique name  within the scope of . The ''structural congruence''  over ambients is the least congruence such that  is a commutative monoid.The operational semantics of pure ambient safe calculus are defined in terms of a reduction relation  by the following axioms and rules.'''Axioms:''';;.'''Rules:''';. denotes a reflexive and transitive closure of the binary relation .A translation from the set  of safe ambients to the set  of membrane configurations is given formally as follows:'''Definition.''' A translation  is given by, where  isAn object  is placed near the membrane structure to prevent the consumption of capability objects in a membrane system whichcorresponds 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: iff .Considering two membrane systems  and  with only one object ,  if there is a sequence of rules , from the particular set of rules used in#References|7, such that applying the rules from this set to the membrane configuration  it is obtained the membrane configuration . '''Proposition.''' If  and  are two ambients and  is a membrane system such that  and , then there exists a set of rules applicable to  such that , and . '''Proposition.''' Let  and  be two membrane systems with only one  object, and an ambient  such that . If there is a set of rules applicable to  such that , then there exists an ambient  with  and . 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 , then . * If , then exists  such that  and .===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 mutualmembranes 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.+''Pino/Exo/Phage Calculus - Its Syntax''----''Systems''        nests of membranes''Branes''        combinations of actions''Actions''        phago , exo Membranes are formed of patches, where a patch  can be composed from other patches . An elementary patch  consists of an action  followed, after the consumption of it, by another patch . Actions often come in complementary pairs which cause the interaction between membranes. The names  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. denotes the set of brane systems defined above. Some abbreviations can be made:  as ,  as , and  as .The structural congruence relation is a way of rearranging the system such that the interacting parts come together, as illustratedin what follows:+''Pino/Exo/Phage Calculus - Structural Congruence''----                              In what follows the reduction rules of the calculus are presented:+''Pino/Exo/Phago Calculus - Reduction Rules''----    '''(Pino)'''    '''(Exo)'''    '''(Phago)'''    '''(Par)'''    '''(Brane)'''    '''(Struct)'''The action  creates an empty bubble within the membrane where the  action resides; imagine that the original membrane buckles towards inside and pinches off. The patch  on the empty bubble is a parameter of . The exo action , which comes with a complementary co-action, 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  gets expelled to the outside, and all the residual patches of the two membranes become contiguous. The phago action , which also comes with a complementary co-action , models a membrane (the one with ) "eating" another membrane (the one with ). Again, the process has to be smooth and continuous, so it is biologicallyimplementable. It proceeds by the  membrane wrapping around the  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  of the co-phago action (similar to the parameter of the pino action).A translation from the set  of brane processes to the set  of membrane configurations is given formally as follows:'''Definition''' A translation  is given by where  is defined as: 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''     ''Exo''     ''Phago''     where  is a multiset and ,  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  is a PEP system and  is a system of mutual membranes with objects on surface, then there exists  such that  and , whenever . '''Proposition.''' If  is a PEP system and  is a system of mutual membranes with objects on surface, then there exists  such that  whenever . '''Remark.''' In the last proposition it is possible that . Suppose . By translation it is obtained that  . It is possible to have  or  such that , but . '''Proposition.''' If  is a PEP system and  is a system of mutual membranes with objects on surface, then there exists  such that  and , whenever . '''Proposition.''' If  is a PEP system and  is a system of mutual membranes with objects on surface, then there exists  such that  whenever .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 . Let us assume . By translation, it is obtained that , such that . It can be observed that there exist  such that , but .These results are presented together with their proofs in #References|2.
References # B. Aman, G.Ciobanu. Describing the Immune System Using Enhanced Mobile Membranes. ''Electr. Notes in Theoretical Computer Science'', vol.194(3), 5–18, 2008.# B. Aman, G.Ciobanu. Membrane Systems with Surface Objects. ''Proc. of the International Workshop on Computing with Biomolecules (CBM 2008)'', 17–29, 2008.# B. Aman, G.Ciobanu. Resource Competition and Synchronization in Membranes. ''Proceedings of SYNASC08'', IEEE Computing Society, 145–151, 2009.# B. Aman, G.Ciobanu. Simple, Enhanced and Mutual Mobile Membranes. ''Transactions on Computational Systems Biology XI', LNBI vol.5750, 26–44, 2009.# B. Aman, G.Ciobanu. Translating Mobile Ambients into P Systems. ''Electr. Notes in Theoretical Computer Science'', vol.171(2), 11–23, 2007.# B. Aman, G.Ciobanu. Turing Completeness Using Three Mobile Membranes. ''Lecture Notes in Computer Science'', vol.5715, 42–55, 2009.# B. Aman, G. Ciobanu. On the Relationship Between Membranes and Ambients. ''Biosystems'', vol.91(3), 515–530, 2008.# 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.# N. Busi, R. Gorrieri. On the computational power of Brane calculi. ''Third Workshop on Computational Methods in Systems Biology'', 106–117, 2005.# L. Cardelli. Brane Calculi. Interactions of biological membranes. ''Lecture Notes in BioInformatics'', vol.3082, 257–278, Springer, 2004.# L. Cardelli, A. Gordon. Mobile Ambients. ''Lecture Notes in Computer Science'', vol.1378, Springer, 140–155, 1998.# 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.# L. Cardelli, S. Pradalier. Where Membranes Meet Complexes. ''BioConcur'', 2005.# M. Cavaliere, S. Sedwards. Membrane Systems with Peripheral Proteins: Transport and Evolution. ''Electr. Notes in Theoretical Computer Science'', vol.171(2), 37–53, 2007.# G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez. ''Application of Membrane Computing''. Springer, 2006.# J. Dassow, Gh. Păun. ''Regulated Rewriting in Formal Language Theory''. Springer-Verlag, 1990.# S.N. Krishna. The Power of Mobility: Four Membranes Suffice. ''Lecture Notes in Computer Science'', vol.3526, 242–251, Springer, 2005.# S.N. Krishna. Membrane computing with transport and embedded proteins. ''Theoretical Computer Science'', vol.410, 355–375, 2009.# S.N. Krishna. Universality results for P systems based on brane calculi operations. ''Theoretical Computer Science'', vol.371, 83–105, 2007.# S.N. Krishna, G. Ciobanu. On the Computational Power of Enhanced Mobile Membranes. ''Lecture Notes in Computer Science'', vol.5028, 326–335, 2008.# S.N. Krishna, Gh. Păun. P Systems with Mobile Membranes. ''Natural Computing'', vol.4(3), 255–274, 2005.# F. Levi, D. Sangiorgi. Controlling Interference in Ambients. ''Proceedings POPL'00'', ACM Press, 352–364, 2000.# F. Levi, D. Sangiorgi. Mobile Safe Ambients. ''ACM TOPLAS'', vol.25, 1-69, 2003.# Gh. Păun. ''Membrane Computing. An Introduction.'' Springer-Verlang, Berlin, 2002.# Gh. Păun. Membrane Computing and Brane Calculi(Some Personal Notes). ''Electr. Notes in Theoretical Computer Science'', vol.171, 3–10, 2007.