The Role of the Environment in Tissue P Systems with Cell Division

The Role of the Environment in Tissue P Systems with Cell Division Mario J. P´erez-Jim´enez1, Agust´ın Riscos-N´u˜nez1, Miquel Rius-Font2, Francisco J. Romero-Campero1 1Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Seville Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected], [email protected], [email protected] 2Department of Applied Mathematics IV Universitat Polit´ecnica de Catalunya, Spain E-mail: [email protected] Summary. Classical tissue P systems with cell division have a special alphabet whose elements appear at the initial configuration of the system in an arbitrary large number of copies. These objects are shared in a distinguished place of the system, called the environment. Besides, the ability of these computing devices to have infinite copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems. This paper deals with computational aspects of tissue P systems with cell division where there is not an environment having the property mentioned above. Specifically, we establish the relationships between the polynomial complexity class associated with tissue P systems with cell division and with or without environment. As a consequence, we prove that it is not necessary to have infinite copies of some objects at the initial configuration in order to solve NP–complete problems in an efficient way. Key words:Membrane Computing, Tissue P Systems, Cell Division, Environment of a tissue, Computational Complexity. 1 Preliminaries An alphabet,Γ, is a non–empty set whose elements are called symbols. An ordered finite sequence of symbols is a string or word. If uand vare strings over Γ, then so is their concatenation uv, obtained by juxtaposition, that is, writing uand vone after the other. The number of symbols in a string uis the length of the string and it is denoted by |u|. As usual, the empty string (with length 0) will be denoted by λ. The set of all strings over an alphabet Γis denoted by Γ∗. In algebraic terms, Γ∗ 90 M.J. P´erez-Jim´enez et al. is the free monoid generated by Γunder the operation of concatenation. Subsets, finite or infinite, of Γ∗are referred to as languages over Γ. The set of symbols occurring in a string u∈Γ∗is denoted by alph(u). The Parikh vector associated with a string u∈Γ∗with respect to the alphabet Σ={a1, . . . , ar} ⊆ Γis ΨΣ(u) = (|u|a1, . . . , |u|ar), where |u|aidenotes the number of ocurrences of symbol aiin string u. This is called the Parikh mapping associated with Σ. Notice that, in this definition, the ordering of the symbols from Σis relevant. If Σ1={ai1, . . . , air} ⊆ Γ, then we define ΨΣ1(u)=(|u|ai1, . . . , |u|air), for each u∈Γ∗. Amultiset mover a set Ais a pair (A, f) where f:A→Nis a mapping. If m= (A, f) is a multiset then its support is defined as supp(m) = {x∈A|f(x)> 0}. A multiset is empty (resp. finite) if its support is the empty set (resp. a finite set). If m= (A, f) is a finite multiset over Aand supp(m) = {a1, . . . , ak}, then it will be denoted as m={af(a1) 1, . . . , af(ak) k}. That is, superscripts indicate the multiplicity of each element, and if f(x) = 0 for x∈A, then element xis omitted. A finite multiset m={af(a1) 1, . . . , af(ak) k}can also be represented by the string af(a1) 1. . . af(ak) kover the alphabet {a1, . . . , ak}. Nevertheless, all permutations of this string identify the same multiset mprecisely. Throughout this paper, we speak about “the finite multiset m” where mis a string, meaning “the finite multiset represented by the string m”. If m1= (A, f1), m2= (A, f2) are multisets over A, then we define the union of m1and m2as m1+m2= (A, g), where g=f1+f2, that is, g(a) = f1(a) + f2(a), for each a∈A. For any sets Aand Bthe relative complement A\Bof Bin Ais defined as follows: A\B={x∈A|x /∈B}. Finally, for any set Awe denote |A|the cardinal (number of elements) of A, as usual. In what follows, we assume the reader is already familiar with the basic notions and terminology of P systems. For details, see [4]. 2 Tissue P Systems with communication rules Definition 2.1 A tissue P system with communication rules of degree q≥1is a tuple Π= (Γ, E,M1, . . . , Mq,R, iout), where: 1. Γis a finite alphabet whose elements are called objects; 2. E ⊆ Γ; 3. M1, . . . , Mqare strings over Γ, representing finite multisets of objects; 4. Ris a finite set of communication rules of the form (i, u/v, j), for i, j ∈ {0,1,2, . . . , q}, i =j,u, v ∈Γ∗,|u|+|v|>0; 5. iout ∈ {0,1,2, . . . , q}. A tissue P system without environment is a tissue P system such that E=∅. In this case, alphabet Ecan be removed from the tuple. The Role of the Environment in Tissue P Systems with Cell Division 91 Atissue P system with communication rules Π= (Γ, E,M1, . . . , Mq,R, iout), of degree q≥1 can be viewed as a set of qcells, labelled by 1, . . . , q, with an environment labelled by 0 such that: (a) M1, . . . , Mqrepresent the finite multisets of objects initially placed in the qcells of the system; (b) Eis the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies; and (c) iout ∈ {0,1,2, . . . , q}represents a distinguished cell or the environment which will encode the output of the system. We use the term region i(0 ≤i≤q) to refer cell iin the case 1 ≤i≤qand to refer the environment in the case i= 0. When applying a rule (i, u/v, j), the objects of the multiset represented by u are sent from region ito region jand, simultaneously, the objects of multiset v are sent from region jto region i. The length of the communication rule (i, u/v, j) is defined as |u|+|v|. A communication rule (i, u/v, j) is called a symport rule if u=λor v=λ. A symport rule (i, u/λ, j), with i= 0, j = 0, provides a virtual arc from cell ito cell j. A communication rule (i, u/v, j) is called an antiport rule if u=λand v=λ. An antiport rule (i, u/v, j), with i= 0, j = 0, provides two arcs: one from cell i to cell jand another one from cell jto cell i. Thus, every tissue P system has an underlying directed graph whose nodes are the cells of the system and the arcs are obtained from communication rules. In this context, the environment can be considered as a virtual node of the graph such that its connections are defined by communication rules of the form (i, u/v, j), with i= 0 or j= 0. The rules of a system like the one above are used in a non-deterministic maximally parallel manner as it is customary in membrane computing. At each step, all cells which can evolve must evolve in a maximally parallel way (at each step we apply a multiset of rules which is maximal, no further applicable rule can be added). An instantaneous description or a configuration at any instant of a tissue P system with communication rules is described by all multisets of objects over Γ associated with all the cells present in the system, and the multiset of objects over Γ− E associated with the environment at that moment. Bearing in mind that the objects from Ehave infinite copies in the environment, they are not properly changed along the computation. The initial configuration is (M1,··· ,Mq;∅). A configuration is a halting configuration if no rule of the system is applicable to it. Let us fix a tissue P system with communication rules Π. We say that configuration C1yields configuration C2in one transition step, denoted C1⇒ΠC2, if we can pass from C1to C2by applying the rules from Rfollowing the previous remarks. A computation of Πis a (finite or infinite) sequence of configurations such that: 1. the first term of the sequence is the initial configuration of the system; 2. each non-initial configuration of the sequence is obtained from the previous configuration by applying the rules of the system in a maximally parallel manner with the restrictions previously mentioned; and 92 M.J. P´erez-Jim´enez et al. 3. if the sequence is finite (called halting computation), then the last term of the sequence is a halting configuration. All computations start from an initial configuration and proceed as stated above; only halting computations give a result, which is encoded by the objects present in the output region iout in the halting configuration. We denote by Comp(Π) the set of computations of the tissue P system Π. If C={Ci}i<r+1 of Π(r∈N) is a halting computation, then the length of C is r, that is, the number of non-initial configurations which appear in the finite sequence C. We denote it by |C|. We also denote by Ci(j) the contents of cell jat configuration Ci. 3 Tissue P Systems with Cell Division Cell division is an elegant process that enables organisms to grow and reproduce. Mitosis is a process of cell division which results in the production of two daughter cells from a single parent cell. Daughter cells are identical to one another and to the original parent cell. Through a sequence of steps, the replicated genetic material in a parent cell is equally distributed to two daughter cells. While there are some subtle differences, mitosis is remarkably similar across organisms. Before a dividing cell enters mitosis, it undergoes a period of growth where the cell replicates its genetic material and organelles. Replication is one of the most important functions of a cell. DNA replication is a simple and precise process that creates two complete strands of DNA (one for each daughter cell) where only one existed before (from the parent cell). Let us recall that the model of tissue P systems with cell division is based on the cell-like model of P systems with membranes division [3]. In these models, the cells are not polarized; the cells obtained by division have the same labels as the original cell, and if a cell is divided, its interaction with other cells or with the environment is locked during the division process. In some sense, this means that while a cell is dividing it closes its communication channels. Definition 3.1 A tissue P system with cell division of degree q≥1is a tuple Π= (Γ, E,M1, . . . , Mq,R, iout), where: 1. Γis a finite alphabet whose elements are called objects; 2. E ⊆ Γ; 3. M1, . . . , Mqare strings over Γ, representing finite multisets of objects; 4. Ris a finite set of rules of the following forms: (a) Communication rules:(i, u/v, j), for i, j ∈ {0,1,2, . . . , q}, i =j,u, v ∈Γ∗, |u|+|v|>0; (b) Division rules:[a]i→[b]i[c]i, where i∈ {1,2, . . . , q},i=iout and a, b, c ∈ Γ; 5. iout ∈ {0,1,2, . . . , q}. The Role of the Environment in Tissue P Systems with Cell Division 93 Atissue P system with cell division is a tissue P system with communication rules where also division rules are allowed. When applying a division rule [a]i→[b]i[c]i, under the influence of object a, the cell with label iis divided into two cells with the same label; in the first copy, object ais replaced by object b, in the second one, object ais replaced by object c; all the other objects residing in cell iare replicated and copies of them are placed in the two new cells. The output cell iout cannot be divided. The rules of a tissue P system with cell division are applied in a nondeterministic maximally parallel manner as it is customary in membrane computing. At each step, all cells which can evolve must evolve in a maximally parallel way (at each step we apply a multiset of rules which is maximal, no further applicable rule can be added), with the following important remark: if a cell divides, then the division rule is the only one which is applied for that cell at that step; the objects inside that cell do not evolve by means of communication rules. In other words, before division a cell interrupts all its communication channels with the other cells and with the environment. The new cells resulting from division will interact with other cells or with the environment only at the next step – providing that they do not divide once again. The label of a cell precisely identifies the rules which can be applied to it. 4 Recognizer Tissue P Systems Let us recall that a decision problem is a pair (IX, θX) where IXis a language over a finite alphabet (whose elements are called instances) and θXis a total boolean function over IX. Many abstract problems are not decision problems. For example, in combinatorial optimization problems some value must be optimized (minimized or maximized). In order to deal with such problems, they can be transformed into roughly equivalent decision problems by supplying a target/threshold value for the quantity to be optimized, and then asking whether this value can be attained. A natural correspondence between decision problems and languages can be established as follows. Given a decision problem X= (IX, θX), its associated language is LX={w∈IX:θX(w) = 1}. Conversely, given a language L, over an alphabet Γ, its associated decision problem is XL= (IXL, θXL), where IXL=Γ∗, and θXL={(x, 1) : x∈L}∪{(x, 0) : x /∈L}. The solvability of decision problems is defined through the recognition of the languages associated with them. In order to study the computing efficiency, the notions from classical computational complexity theory are adapted for membrane computing, and a special class of cell-like P systems is introduced in [7]: recognizer P systems (called accepting P systems in a previous paper [6]). For tissue P systems, with the same idea as recognizer cell-like P systems, recognizer tissue P systems is introduced in [5]. Definition 4.1 Arecognizer tissue P system with cell division of degree q≥1is a tuple Π= (Γ, Σ, E,M1,...,Mq,R, iin, iout), where: 94 M.J. P´erez-Jim´enez et al. •(Γ, E,M1, . . . , Mq,R, iout)is a tissue P system with cell division of degree q≥1, as defined in the previous section. •The working alphabet Γhas two distinguished objects yes and no, at least one copy of them present in some initial multisets M1, . . . , Mq, but none of them is present in E. •Σis an (input) alphabet strictly contained in Γsuch that E ∩ Σ=∅. • M1, . . . , Mqare strings over Γ\Σ. •iin ∈ {1, . . . , q}is the input cell. •The output region iout is the environment. In the case of tissue without environment, iout is a distinguished cell, that is iout ∈ {1, . . . , q}. •All computations halt. •If Cis a computation of Π, then either object yes or object no (but not both) must have been released into the environment, and only at the last step of the computation. For each multiset mover Σ, the computation of the system Πwith input mstarts from the configuration of the form (M1,M2, . . . , Miin +m, . . . , Mq;∅), that is, the input multiset mhas been added to the contents of the input cell iin, and we denote it by Π+m. Therefore, we have an initial configuration associated with each input multiset m(over the input alphabet Σ) in this kind of systems. Given a recognizer tissue P system with cell division, and a halting computation C={Ci}i<r+1 of Π(r∈N), we define the result of Cas follows: Output(C) =        yes,if Ψ{yes,no}(Mr,iout ) = (1,0) ∧ Ψ{yes,no}(Mi,iout ) = (0,0) for i= 0, . . . , r −1 no,if Ψ{yes,no}(Mr,iout ) = (0,1) ∧ Ψ{yes,no}(Mi,iout ) = (0,0) for i= 0, . . . , r −1 where Ψis the Parikh mapping, and Mi,iout is the multiset over Γ\ E associated with the output region at the configuration Ci, in particular, Mr,iout is the multiset over Γ\ E associated with the output region at the halting configuration Cr. We say that a computation Cis an accepting computation (respectively, rejecting computation) if Output(C) = yes (respectively, Output(C) = no), that is, if object yes (respectively, object no) appears in the output region associated with the corresponding halting configuration of C, and neither object yes nor no appears in the output region associated with any non–halting configuration of C. Let us notice that if a recognizer tissue P system Π= (Γ, Σ, E,M1, . . . , Mq,R, iin, iout) has a rule of the type (i, λ/u, 0) then alph(u)∩(Γ\E)=∅, because on the contrary all computations of Πwould be non halting. For each natural number k≥1, we denote by TDC(k) the class of recognizer tissue P systems with cell division and with communication rules of length at most k. In the case of tissue P systems without environment, we denote by \ TDC(k) the class of recognizer tissue P systems with cell division and with communication rules of length at most k. The Role of the Environment in Tissue P Systems with Cell Division 95 5 Polynomial Complexity Classes of Tissue P systems Next, we define what solving a decision problem in the framework of tissue P systems in a uniform and efficient way means. Bearing in mind that they provide devices with a finite description, a numerable family of tissue P systems will be necessary in order to solve a decision problem. Definition 5.1 We say that a decision problem X= (IX, θX)is solvable in a uniform way and polynomial time by a family Π={Π(n)|n∈IN}of recognizer tissue P systems (with symport/antiport rules, with cell division or with cell separation) if the following holds: •The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(n)from n∈IN. •There exists a pair (cod, s)of polynomial-time computable functions over IX such that: −for each instance u∈IX,s(u)is a natural number, and cod(u)is an input multiset of the system Π(s(u)); −for each n∈IN,s−1(n)is a finite set; −the family Πis polynomially bounded with regard to (X, cod, s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) with input cod(u)is halting and it performs at most p(|u|)steps; −the family Πis sound with regard to (X, cod, s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then θX(u) = 1; −the family Πis complete with regard to (X, cod, s), that is, for each u∈IX, if θX(u)=1, then every computation of Π(s(u)) with input cod(u)is an accepting one. From the soundness and completeness conditions above we deduce that every P system Π(n) is confluent, in the following sense: every computation of a system with the same input multiset must always give the same answer. Let Rbe a class of recognizer tissue P systems. We denote by PMCRthe set of all decision problems which can be solved in a uniform way and polynomial time by means of families of systems from R. The class PMCRis closed under complement and polynomial–time reductions [6]. Next, we prove a technical result concerning recognizer tissue P systems. Lemma 5.2 Let Π={Π(n)|n∈IN}a family of recognizer tissue P systems solving a decision problem X= (IX, θX)in polynomial time according to the previous definition. Let (cod, s)a polynomial encoding associated with that solution. Let r(n)be a polynomial function such that for each u∈IXevery computation of Π(s(u)) + cod(u)is halting and it performs at most r(|u|)steps. Then, there exists a polynomial function p(n)such that for each instance u∈IX,2p(|u|)is an 96 M.J. P´erez-Jim´enez et al. upper bound of the number of objects from Ewhich are moved from the environment to all cells of the system Π(s(u))+cod(u)by communication rules along any computation. Proof: Let u∈IXbe an instance of Xand Π(s(u)) + cod(u) = (Γ, Σ, E,M1, . . . , Mq,R, iin, iout) Let k∈IN be such that Π(s(u)) + cod(u)∈TDC(k). Let M=|M1+· · · +Mq|. Then, any computation of Π(s(u)) + cod(u) performs, at most, r(|u|) transition steps. Let C= (C0,C1,...,Cm), 0 ≤m≤r(|u|), be a computation of Π. For each t, 0 ≤t≤mand i, 1 ≤i≤q, we denote by Ct(i) the multiset of objects over Γ in cell iat time t. We also denote Ct(0) the multiset of objects over Γ\ E in the environment at time t. Let us suppose that we apply only communication rules at mconsecutive transition steps. At this situation, for each t(0 ≤t≤m) we compute an upper bound of |Ct(0) + Ct(1) + . . . +Ct(q)|. Then, for each i, j (0 ≤i, j ≤q, i =j) we denote by At(i, j) the multiset of objects being moved from region jto region iby applying rules of the type (i, u/v, j) at time t. Let us construct αt, 0 ≤t≤m, an upper bound of the number of objects which appear in the whole system (taking all cells into account) at time t. That is, αt≥ |Ct(0) + Ct(1) + ...+Ct(q)| The construction is made by induction on t. For t= 0 we consider α0=M. Let tbe such that 0 ≤t < m and for each t′(0 ≤t′≤t) let us assume that we have constructed αt′such that αt′≥ q ∑ i=0 |Ct′(i)| The number of objects moved into cell i(1 ≤i≤q) at instant t+ 1 is At(i, 0) + q ∑ j=1,j=i At(i, j) The number of objects sent to the environment at instant t+ 1 is q ∑ j=1 At(0, j). Notice that objects coming to region ifrom some other cell jwere already present in the previous configuration. Besides, in order to trigger a communication rule bringing objects from the environment into region i, at least one object in region iis required, or else one symbol from Γ\ E in the environment. Finally, recall that the length of communication rules is bounded by k. From these considerations, we deduce: q ∑ i=1 q ∑ j=1,j=i |At(i, j)| ≤ αtand q ∑ i=1 |At(i, 0)| ≤ αt·k The Role of the Environment in Tissue P Systems with Cell Division 97 Besides, q ∑ j=1 |At(0, j)| ≤ αt·k Then, we can consider αt+1 =αt+αt·k+αt·k=αt·(1 + 2k). Thus, for each t(0 ≤t≤m) we define αt=M·(1 + 2k)t. Hence, if we applied in a consecutive way the maximum possible number of communication rules (without applying any division rules) to the system Π(s(u)) + cod(u), in any instant of any computation of the system, M·(1 + 2k)r(|u|)is an upper bound of the number of objects in the whole system. Now, let us consider the effects of applying in a consecutive way the maximum possible number of division rules (without applying any communication rules) to the system Π(s(u)) + cod(u) when the initial configuration has M·(1 + 2k)r(|u|) objects. After that, an upper bound of the number of objects in the whole system by any computation is M·(1 + 2k)r(|u|)·2r(|u|)·r(|u|). Hence, for each instance u∈IXthe number of objects from Ewhich are moved from the environment to the whole cells of the system Π(s(u))+cod(u) is, at most, M·(1+2k)r(|u|)·2r(|u|)·r(|u|). Then, we consider a polynomial function p(n) such that p(|u|)≥log(M) + r(|u|)·log(1 + 2k) + r(|u|) + log(r(|u|)) for each instance u∈IX. The polynomial function p(n) fulfills the property required at the Lemma.  6 Simulating tissue P systems with cell division by means of tissue P systems with cell division and without environment The goal of this section is to show that any tissue P system with cell division can be simulated by a tissue P system with cell division and without environment in an efficient way. First of all, we define the meaning of efficient simulations in the framework of recognizer tissue P systems. Definition 6.1 Let Πand Π′be recognizer tissue P systems. We say that Π′ simulates Πin an efficient way if the following holds: 1. Π′can be constructed from Πby a deterministic Turing machine working in polynomial time. 2. There exists an injective function, f, from the set Comp(Π)of computations of Πonto the set Comp(Π′)of computations of Π′such that: ⋆There exists a deterministic Turing machine that constructs computation f(C)from computation Cin polynomial time. ⋆A computation C ∈ Comp(Π)is an accepting computation if and only if f(C)∈Comp(Π′)is an accepting one. 104 M.J. P´erez-Jim´enez et al. other objects in the cell are duplicated except the object that activate the cell division operation. In this paper, the computational efficiency of tissue P systems with cell division and without environment has been studied. We conclude that the environment of tissue P systems can be removed without a loss of efficiency. For future work, we plan to do further research in the study of tissue P systems with cell separation. Let us recall that, in this kind of systems, the application of separation rules only duplicates the cell while the objects are not replicated. They are simply distributed according to a prefixed criterion. Acknowledgements The work was supported by Project TIN2009-13192 of the Ministerio de Ciencia e Innovaci´on of Spain and Project of Excellence with Investigador de Reconocida Val´ıa, from Junta de Andaluc´ıa, grant P08 – TIC 04200. References 1. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J. and Romero-Campero, F.J. A linear solution for QSAT with Membrane Creation. Lecture Notes in Computer Science 3850, (2006), 241–252. 2. Pan, L. and Ishdorj, T.-O. P systems with active membranes and separation rules. Journal of Universal Computer Science,10, 5, (2004), 630–649. 3. P˘aun, Gh. Attacking NP-complete problems. In Unconventional Models of Computation, UMC’2K (I. Antoniou, C. Calude, M. J. Dinneen, eds.), Springer-Verlag, 2000, 94-115. 4. P˘aun, Gh. Membrane Computing. An Introduction. Springer–Verlag, Berlin, (2002). 5. P˘aun, Gh., P´erez-Jim´enez, M.J. and Riscos-N´u˜nez, A. Tissue P System with cell division. In. J. of Computers, communications &control,3, 3, (2008), 295–303. 6. P´erez-Jim´enez, M.J., Romero-Jim´enez, A. and Sancho-Caparrini, F. Complexity classes in models of cellular computing with membranes. Natural Computing,2, 3 (2003), 265–285. 7. P´erez-Jim´enez, M.J., Romero-Jim´enez, A. and Sancho-Caparrini, F. A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics,11, 4, (2006), 423-434.