A Case Study in (Mem)Brane Computation: Generating Squares of Natural Numbers

A Case Study in (Mem)Brane Computation: Generating Squares of Natural Numbers Nadia Busi1and Miguel A. Guti´errez-Naranjo2 1Dipartimento di Scienze dell’Informazione - Universit`a di Bologna Mura Anteo Zamboni 7, I-40127 Bologna, Italy [email protected] 2Dpto. de Ciencias de la Computaci´on e Inteligencia Artificial Universidad de Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain [email protected] Abstract. The aim of this paper is to start an investigation and a comparison of the expressiveness of the two most relevant formalisms inspired by membranes interactions, namely, P systems and Brane Calculi. We compare the two formalisms with respect to their ability to act as generator devices. In particular, we show different ways of generating the set L={n2|n≥1}in P systems and in Brane Calculi. 1 Introduction Natural Computing studies new computational paradigms inspired from various well known natural phenomena in physics, chemistry, and biology. It abstracts the way in which nature computes, conceiving new computing models. There are several fields in Natural Computing that are now well established. Among them, we mention Genetic algorithms introduced by J. Holland [7] that is inspired by natural evolution and selection in order to find a good solution in a large set of feasible candidate solutions, Neural Networks introduced by W.S. McCulloch and W. Pitts [8] which is based on the interconnections of neurons in the brain, and DNA-based molecular computing, that was born when L. Adleman [1] published a solution to an instance of the Hamiltonian path problem by manipulating DNA strands in a lab. This paper is devoted to a new field in Natural Computing. Starting from the structure and functioning of cells as living organisms able to process and generate information, two different branches of Natural Computing were recently initiated: Membrane Computing and Brane Calculi. Membrane Computing was introduced by Gh. P˘aun in [9]; a comprehensive presentation1 can be found at [11]. The devices of this model are called Psystems. Roughly speaking, a P system consists of a membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous non-deterministic maximally parallel manner. 1 A layman-oriented introduction can be found in [10] and further bibliography at [14]. Brane Calculi were introduced by L. Cardelli in [4] on the assumption that in living cells membranes are not merely containers, they are highly dynamic and participate actively in the cell life. In this way, computation happens on the membrane, not inside of it. The first attempt of bridging the two research areas was made in [6] by the fathers of the two disciplines, L. Cardelli and Gh. P˘aun. As they point out, Membrane Computing and Brane Calculi have different objectives and develop in different directions. While Membrane Computing tries to abstract computing models, in the Turing sense, from the structure and the functioning of the cell (...), Brane Calculi pay more attention to the fidelity to the biological reality (...). In that paper [6], four basic operations from Brane Calculi, namely, pino,exo, mate and drip, are expressed in terms on the Membrane Computing formalism and the Turing completeness of systems which use the mate,drip operations is shown. The Turing universality of Brane Calculi (in fact, by using only phago and exo operations) was proved in [3]. Recently, it has been proved that P systems with mate and drip operations and using at most five membranes during any step of a computation are universal (see [2]). This result improves a similar one from [6] were eleven membranes are used. In some sense, in this paper we cross the bridge in the other way. Instead of expressing Brane Calculi operations in terms of the Membrane Computing formalism, we take a problem from computability, the generation of a set of numbers, and we show how it can be handled both in Membrane Computing and in Brane Calculi. The paper is organized as follows: first the case study, i.e., the set L= {n2|n≥1}and some considerations with respect to the codifications are fixed in the next section. In Section 3, two different Membrane Computing devices that generate Lare shown. Inspired on the second Membrane Computing design, two Brane Calculi devices that generate Lare presented in Section 4. Some final remarks are presented in the last section. 2 The Case Study Computational devices can be designed in order to perform different tasks. Among such tasks, they can be designed to solve decision problems (IX,θ X) where IXis a language over a finite alphabet (whose elements are called instances)andθXis a total boolean function over IX. In a more general case, the function is not boolean and the problem consists on the computation of a function ffrom IXonto a general set S. Another type of tasks is the generation of various sets (of numbers, vectors, strings, etc.). Due to the nondeterminism, several different computations are obtained and some piece of information is considered as the output. Collecting all (acceptable) outputs, we get a set (of numbers, vectors, strings, etc.) generated by the computation device. In order to fix ideas, let us consider the case study used in this paper. We will consider the set {n2|n≥1}. For its generation, we will design appropriate devices in the computational models Membrane Computing and Brane Calculi. Such devices are non-deterministic and several computations can be performed from the starting point. In each device, a piece of information will be considered the output of the system. In the case of Membrane Computing, the output is codified as the number of objects inside a fixed membrane in a halting configuration. In the Brane Calculi device, the output is codified as the number of membranes of a specific kind that are present in the system in a halting computation. The set of all possible outputs of the device is exactly L={n2|n≥1}.Inthisway, Lis the set generated by the device. 3 Membrane Computing In Membrane Computing, many different types of rules and different semantics have been presented. The choice of these rules and semantics lead us to different models of P systems. In this section we present two P systems constructed in two different models that generate the set {n2|n≥1}. In these examples several types of rules are used (Ois the alphabet of objects, His a finite set of labels,andλis the empty string): –Object evolution rules [a→v]hwhere h∈H,a∈O,andvis a string over Odescribing a multiset of objects. They are associated with membranes and depending only on the label of the membrane. Using such a rule means that an object aevolves to the multiset vinside the membrane with label h. –Cooperation rules: [v→w]hwhere h∈Hand v,w are string over Odescribing a multisets of objects. This rule is similar to the previous one, but in this type, the rule is triggered by a multiset of objects whereas in an object evolution rule only one object is necessary for triggering it. –Dissolution rules: [a]h→bwhere h∈H,a∈O,b∈O∪{λ}. The object ainside the membrane labeled with hproduces the dissolution of the membrane and it is transformed into the object b. This object btogether with the remaining objects in the membrane hare placed inside the surrounding membrane. –Send-in communication rules: a[] h→[b]hwhere h∈H,a, b ∈O.An object aout of the membrane labeled with his sent into the membrane and transformed into b. –Send-out communication rules: [a]h→[] hbwhere h∈H,a, b ∈O.Thisis dual to the previous case. An object ainside the membrane labeled with h is sent out of the membrane and transformed into b. Rules are applied according to the following principles: –Rules are used as usual in the framework of Membrane Computing, that is, in a maximally parallel way. In one step, each object in a membrane can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can evolve by a rule of any form must do it (with the restrictions indicated below). –If a membrane is dissolved, its content (multiset and internal membranes) becomes part of the immediately external one. The skin membrane is never dissolved. –All the elements which are not involved in any of the operations to be applied remain unchanged. –Several rules can be applied to different objects in the same membrane simultaneously. The exception are the division rules since a membrane can be dissolved only once. In order to generate a set, an output membrane is fixed and the number of objects in it is counted when the system halts. The number of objects can vary from one computation to other due to the nondeterminism of the system. In the next examples, the set of numbers obtained in the output membrane, i.e., the generated set, is {n2|n≥1}. 3.1 Cooperation and Priorities The first P system that we show is taken from [11] (p. 75) and it uses two of the most powerful features in P systems. The first one is the use of rules with cooperation between objects as described above. This type of rules are not triggered by the occurrence of only one object, but two or more objects are necessary in order to trigger the rule. The second feature is the priority among rules. In the general framework of Membrane Computing, if two rules can be applied, one of them is chosen in a non-deterministic way. If a priority between rules is added, we decrease the non-determinism, since we have a precedence between them. With the notation fixed above, the P system is Π=(O,H,μ,w1,w 2,w 3,1,R) where O={a, b, d, e, f}is the set of objects, H={1,2,3}is the set of labels, μ= [[[ ]3]2]1is the membrane structure, w1=∅,w2=∅,w3=af are the multisets placed in the membranes at the starting point, 1 is the label of the output membrane,andRis the set of rules: Rule 1: [a→ab]3Rule 5: [b→d]2 Rule 2: [a]3→bRule 6: [d→de]2 Rule 3: [f→ff]3Rule 7: [ff →f]2 Rule 4: [d]1→d[] 1Rule 8: [f]2→λ with the priority (Rule 7: [ff →f]2)>(Rule 8: [f]2→λ) Rules 1,3,5and 6are object evolution rules.Rule7is a cooperation rule: we need two objects fin order to trigger the rule. Rules 2and 8are dissolution rules. Finally, rule 4is a send-out communication rule. The computation is performed as follows. In the initial configuration we only have objects af in the membrane labeled with 3. C0=[[[af ]3]2]1 Due to rule 3, the object fdeterministically evolves to ff. For the object awe have two possibilities: By application of rule 1, the object aevolves to ab or by applying rule 2, membrane 3 dissolves. If we iterate the use of rules 1and 3, after nsteps, n≥0, we get noccurrences of b,onecopyofa,and2 noccurrences of fin membrane 3. C1=[[[abf2]3]2]1 C2=[[[ab2f4]3]2]1 ... Cn=[[[abnf2n]3]2]1 If then rule 2is chosen, the membrane labeled with 3 is dissolved after the evolution of f. With the dissolution, the 2n+1 copies of object fand the n+1 copies of bbecome occurrences of objects of membrane 2. Cn+1 =[[bn+1f2n+1 ]2]1 In one step, the n+ 1 copies of bare transformed into n+ 1 copies of dby rule 5, while the number of occurrences of fis halved. Cn+2 =[[dn+1f2n]2]1 In the next step each occurrence of dintroduces one occurrence of eand the number of occurrences of fis halved again. Cn+3 =[[dn+1en+1f2n−1]2]1 After napplications of rule 7,[ff →f]2, only one copy of object fis present in membrane labeled with 2. In the meantime, rule 6is applied n+1timesin each step. Cn+4 =[[dn+1e2(n+1)f2n−2]2]1 Cn+5 =[[dn+1e3(n+1)f2n−3]2]1 ... Following the priority relation, rule 7[ff →f]2is used as much as possible; when only one object fremains, rule 8is used. C2n+2 =[[dn+1en(n+1)f]2]1 C2n+3 =[dn+1e(n+1)2]1 With the dissolution of membrane 2, all the objects dbecome objects of membrane 1. In the next step, rule 4is applied n+ 1 times and all copies of dare sent out to the environment. C2n+4 =[e(n+1)2]1dn+1 No further step is possible and the computation stops. In the membrane labeled with 1 we have (n+1)(n+1) copies of object efor some n≥0, hence the set generated is {n2|n≥1}. 3.2 A Simplified Solution Now we present a new solution to the same problem. We do not use cooperation or priorities. Only send-in communication, dissolution and object evolution rules are applied. The design is based on the well-known property of natural numbers n  k=0 (2k+1)=(n+1) 2for all n≥0 The P system is the following: Π=(O, H,μ,we,w r,w s,r,R)withthesetof objects O={a, b, c, z},thesetoflabelsH={e, r, s}, the membrane structure μ=[[] e[] r]s. The initial multisets are we=a2bz,wr=∅and ws=∅, i.e., the membranes sand rare empty and there exist two copies of aand one copy of b and zin the membrane e.Theoutput membrane is labeled with rand the set of rules Ris the following: Rule 1: [a→ab ]eRule 5: [a→λ]s Rule 2: [b→bc ]eRule 6: [b→λ]s Rule 3: [z→z]eRule 7: c[] r→[c]r Rule 4: [z]e→λ Note that the only non-determinism in this example is produced by the object z. This object can trigger two rules. The first one is [z→z]ewhich represents that the object zinside the membrane edoes not change. The second one is [z]e→λwhich means that the object zdissolves the membrane e. The collateral effect of the application of this rule is that the remaining objects in eare sent to s. The initial configuration is C0=[[a2bz ]e[] r]s. In the first step the two objects aevolve according to the rule 1,[a→ab ]e, and the object bevolves following the rule 2,[b→bc ]e. These evolutions are deterministic. For the object zwe have two options, rules 3and 4. Let us suppose that zremains unchanged following rule 3,[z→z]e. We obtain the configuration C1=[[a2b3cz ]e[] r]s. Let us suppose that in the next steps the object zdoes not dissolve the membrane e.WeobtainC2=[[a2b5c4z]e[] r]s,C3=[[a2b7c9z]e[] r]s,...and in general, if the element zdoes not dissolves the membrane e,inthen-th (n≥1) step we reach the configuration Cn=[[a2b2n+1cn2z]e[]r]s Let us now suppose that in the n-th step the object zdissolves the membrane eby using rule 4. Since the dissolution is considered after the evolution of objects aand b, we reach the configuration Cn+1 =[a2b2(n+1)+1c(n+1)2z[]r]sn≥0 One of the effects of the dissolution is that the objects a,b,andcare now in the membrane s. On one hand the rules [a→λ]sand [b→λ]sare triggered in the next step, so objects aand bdisappear. On the other hand, objects care in the region surrounding the membrane r, so the communication rule c[] r→[c]r are applied and all the elements cgo into membrane r. In this way, the next configuration is Cn+2 =[[c(n+1)2]r]swith n≥0. No more rules can be applied, so this is a halting configuration and we have computed the number n2with n≥1 (encoded by the elements c) in the output membrane. 4 Brane Calculi In this section we tackle the problem of generating the set {n2|n≥1}in Brane Calculi. Brane Calculi [4] are a family of process calculi proposed for modeling the behavior of biological membranes. In a process algebraic setting, Brane Calculi represent an evolution of BioAmbients [12], a variant of Mobile Ambients [5] based on a set of biologically inspired primitives of interaction. The main novelty of Brane calculi consists in the fact that the active entities reside on membranes, and not inside membranes. In this paper we are interested in the membrane operations of two basic instances of Brane calculi proposed in [4]: the Phago/Exo/Pino (PEP) and the Mate/Bud/Drip (MBD) calculi. The interaction primitives of PEP are inspired by endocytosis (the process of incorporating external material into a cell by engulfing it with the cell membrane) and exocytosis (the reverse process). A relevant feature of such primitives is bitonality, a property ensuring that there will never be a mixing of what is inside a membrane with what is outside, although external entities can be brought inside if safely wrapped by another membrane. As endocytosis can engulf an arbitrary number of membranes, it turns out to be a rather uncontrollable process. Hence, it is replaced by two simpler operations: phagocytosis, that is engulfing of just one external membrane, and pinocytosis, that is engulfing zero external membranes. The primitives of MBD are inspired by membrane fusion (mate) and fission (mito). Because membrane fission is an uncontrollable process that can split a membrane at an arbitrary place, it is replaced by two simpler operations: budding, that is splitting off one internal membrane, and dripping, that consists in splitting off zero internal membranes. An encoding of the MBD primitives in PEP is provided in [4]. 4.1 Basic Brane Calculi: Syntax and Semantics In this section we recall the syntax and the semantics of Brane Calculi [4]. A system consists of nested membranes, and a process is associated to each membrane. Definition 1. The set of systems is defined by the following grammar: P,Q ::= |P◦Q|!P|σP The set of membrane processes is defined by the following grammar: σ, τ ::= 0 |σ|τ|!σ|a.σ Variables a, b range over actions that will be detailed later. The term represents the empty system; the parallel composition operator on systems is ◦. The replication operator ! denotes the parallel composition of an unbounded number of instances of a system. The term σPdenotes the membrane that performs process σand contains system P. The term 0 denotes the empty process, whereas |is the parallel composition of processes; with !σwe denote the parallel composition of an unbounded number of instances of process σ.Terma.σ is a guarded process: after performing the action a, the process behaves as σ. We adopt the following abbreviations: with awe denote a.0, with Pwe denote 0P,andwithσwe denote σ. The structural congruence relation on systems and processes is defined as follows:2 Definition 2. The structural congruence ≡is the least congruence relation satisfying the following axioms: P◦Q≡Q◦Pσ|τ≡τ|σ P◦(Q◦R)≡(P◦Q)◦Rσ|(τ|ρ)≡(σ|τ)|ρ P◦≡Pσ|0≡σ !≡ !0 ≡0 !(P◦Q)≡!P◦!Q!(σ|τ)≡!σ|!τ !!P≡!P!!σ≡!σ P◦!P≡!Pσ|!σ≡!σ 0≡ Definition 3. The basic reaction rules are the following: (par)P→Q P◦R→Q◦R (brane)P→Q σP→σQ (strucong)P≡PP→QQ≡Q P→Q 2With abuse of notation we use ≡to denote both structural congruence on systems and structural congruence on processes. Rules (par) and (brane) are the contextual rules that permit to a system to execute also if it is in parallel with another process or if it is inside a membrane, respectively. Rule (strucong) ensures that two structurally congruent systems have the same reactions. With →∗we denote the reflexive and transitive closure of a relation →. We say that a system Pis deterministic iff for all P,P:ifP→Pand P→P then P≡P.WesaythatPhas a halting computation (or a deadlock) if there exists Qsuch that P→∗Qand Q→. The system Pis a derivative of the system Pif P→∗P;thesetofderivatives of a system Pis denoted by Deriv(P). The Phago/Exo/Pino Calculus (PEP). The PEP calculus is inspired by endocytosis/exocytosis. Endocytosis is the process of incorporating external material into a cell by “engulfing” it with the cell membrane, while exocytosis is the reverse process. As endocytosis can engulf an arbitrary amount of material, giving rise to an uncontrollable process, in [4] two more basic operations are used: phagocytosis, engulfing just one external membrane, and pinocytosis, engulfing zero external membranes. Definition 4. Let Name be a denumerable set of ambient names, ranged over by n,m,.... The set of actions of PEP is defined by the following grammar: a::= C ← n| C ← ⊥ n(σ)| C → n| C → ⊥ n|◦(σ) Action C ← ndenotes phagocytosis; the co-action C ← ⊥ nis meant to synchronize with C ← n;namesnare used to pair-up related actions and co-actions. The co-phago action is equipped with a process σ, this process will be associated to the new membrane that engulfs the external membrane. Action C → ndenotes exocytosis, and synchronizes with the co-action C → ⊥ n. Exocytosis causes an irreversible mixing of membranes. Action ◦ denotes pinocytosis. The pino action is equipped with a process σ: this process will be associated to the new membrane, that is created inside the membrane performing the pino action. Definition 5. The reaction relation for PEP is the least relation containing the following axioms, and satisfying the rules in Definition 3: (phago) C ← n.σ|σ0P◦ C ← ⊥ n(ρ).τ|τ0Q→τ|τ0ρσ|σ0P◦Q (exo) C → ⊥ n.τ|τ0 C → n.σ|σ0P◦Q→P◦σ|σ0|τ|τ0Q (pino)◦(ρ).σ|σ0P→σ|σ0ρ◦P The Mate/Bud/Drip Calculus (MBD). The MBD calculus is inspired by membrane fusion and splitting. To make membrane splitting more controllable, in [4] two more basic operations are used: budding, consisting in splitting off one internal membrane, and dripping, consisting in splitting off zero internal membranes. Membrane fusion, or merging, is called mating. Membrane Computing are more interested in the study of computational devices, by taking the cell as inspiration whereas Brane Calculi try to stay as close to the Biology as possible. In a certain sense, Brane Calculi are dual to Membrane Computing, since they work with object placed on membranes, not with object placed in the regions surrounded by membranes. This is a key difference. In Membrane Computing, the objects represent chemicals swimming in an aqueous solution inside the membranes and membranes separate the compartments where local rules are applied. In Brane Calculi, objects are placed on membranes and they correspond to proteins embedded in the real membranes. The computation is made by membrane operations controlled by these objects. Another notable difference between Brane Calculi and P systems is concerned with the semantics of the two formalism: 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). In this paper we started a joint investigation of both formalisms inspired by the behavior of biological membranes. In particular, we investigate their computational power w.r.t. their ability to generate sets of numbers, and we take as a case study the set L={n2|n≥1}. First we recalled the P systems presented in [11] which generates L,thenwe provided a new, simplified solution. Then we move to Brane Calculi, and we tackle the problem of presenting a solution to the case study based on the simplified solution we propose for P systems. After discussing the problems which arise when moving from P systems to Brane Calculi, we present two solutions of the problem in Brane Calculi. The most relevant problem is due to the shift from the maximal parallelism semantics of P systems to the interleaving semantics of Brane Calculi: while maximal parallelism turns out to be a very powerful synchronization tool, permitting to synchronize an unbounded number of components, it seems that this form of synchronization turns out to be problematic in Brane Calculi. We solve this problem by moving from a “flat” representation of the system to a hierarchical representation, that can be easily obtained by making use of an unbounded number of membranes. We think that the present paper could represent a first step in the comparison of the two aforementioned formalisms. As future work, we plan to investigate the possibility to compute NP-complete problems in polynomial time with Brane Calculi, by taking as a starting point the encouraging results on this topic obtained for P systems (see, for example, [13] and references therein). Acknowledgement The second author acknowledges the support by Project TIN2005-09345-C03-01 of the Ministry of Education and Science of Spain, cofinanced by FEDER funds, and by the Project of Excellence TIC-581 of the Junta de Andaluc´ıa. References 1. L.M. Adleman. Molecular computations of solutions to combinatorial problems. Science, 226 (1994), 1021–1024. 2. D. Besozzi, N. Busi, G. Franco, R. Freund, Gh. P˘aun. Two universality results for (mem)brane systems. In Proceedings of the Fourth Brainstorming Week on Membrane Computing, Vol. I (M.A. Guti´errez Naranjo, Gh. P˘aun, A. Riscos-N´u˜nez, F.J. Romero-Campero, eds.), F´enix Editora, 2006, 49–62. 3. N. Busi, R. Gorrieri. On the computation power of brane calculi. Third Workshop on Computational Methods in Systems Biology, Edinburgh, 2005. 4. L. Cardelli. Brane calculi. In Computational Methods in Systems Biology 2004 (V. Danos, V. Schachter, eds.), LNBI 3082, Springer-Verlag, Berlin, 2005, 257–278. 5. L. Cardelli and A.D. Gordon. Mobile ambients. Theoretical Computer Science, 240, 1 (2000), 177–213. 6. L. Cardelli, Gh.P˘aun. An universality result for a (mem)brane calculus based on mate/drip operations. Intern. J. Found. Computer Sci., 17, 1 (2006), 49–68. 7. J.H. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press, 1975. 8. W.S. McCulloch, W. Pitts. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5 (1943) 115–133. 9. Gh. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 10. Gh. P˘aun, M.J. P´erez-Jim´enez. Recent computing models inspired from biology: DNA and membrane computing. Theoria, 18 (2003), 72–84. 11. Gh. P˘aun. Membrane Computing – An Introduction Springer-Verlag, Berlin, 2002. 12. A. Regev, E. M. Panina, W. Silverman, L. Cardelli, E. Shapiro. BioAmbients: An abstraction for biological compartments. Theoretical Computer Science, 325, 1 (2004), 141–167. 13. A. Riscos-N´u˜nez. Cellular Programming: Efficient Resolution of Numerical NP- Complete Problems. Ph.D. Thesis. University of Seville, 2004. 14. P systems web page http://psystems.disco.unimib.it/