The role of the direction in tissue P systems with cell separation

Journal of Automata, Languages and Combinatorics 19 (2014) 1–4, 185–199 c Otto-von-Guericke-Universit¨at Magdeburg THE ROLE OF THE DIRECTION IN TISSUE P SYSTEMS WITH CELL SEPARATION L. F. Mac´ ıas-Ramos, M. A. Mart´ ınez-del-Amor, M. J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, and L. Valencia-Cabrera Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Av. Reina Mercedes s/n, 41012 Sevilla, Spain e-mail: {lfmaciasr,mdelamor,marper,ariscosn,lvalencia}@us.es ABSTRACT Tissue P systems with cell separation where the communication among cells is performed by means of symport and antiport rules are able to efficiently solve computationally hard problems in a feasible time by a space-time trade off. Symport and antiport rules formally capture the cases where a number of chemical substances pass through a membrane at the same time, with the help of each other, either in the same direction (symport) or in opposite directions (antiport). The present paper investigates the role of the direction in communication rules from a computational complexity point of view. More precisely, the efficiency of tissue P systems with cell separation is analyzed in the case when their communication rules are all of the same type: either symport rules or antiport rules. The main result is that in the framework of tissue P systems with cell separation, passing from using only symport rules to using only antiport rules amounts to passing from non-efficiency to efficiency, assuming that P6=NP. Keywords: Membrane Computing, Tissue P Systems, Cell Separation, Symport/antiport rules. Computational complexity 1. Introduction Membrane Computing is an emergent branch of Natural Computing introduced by Gh. P˘aun at the end of 1998. It is inspired by the structure and functioning of living cells, and provide unconventional distributed, parallel, synchronous and nondeterministic computing devices, called P systems. The basic model consists of a hierarchical structure (a rooted labeled tree) composed by several membranes (the nodes of the tree), embedded into a main membrane called the skin (the root of the tree), and delimiting compartments/regions (space between a membrane and the immediately inner membranes, if any) in which one places multisets of objects. The objects evolve and pass through membranes in a synchronous parallel manner according to given evolution rules, also associated with the membranes. 186 L. F. MAC´ıAS, M. A. MART´ıNEZ, M. J. P´ EREZ, A. RISCOS, L. VALENCIA Tissue P systems considered in this paper have two biological justifications: intercellular communication and cooperation between neurons. The common mathematical model of these two mechanisms is a net of processors (cells) dealing with symbols (chemical substances) and communicating these symbols by means of symport and antiport rules which were introduced to P systems in [7]. Moreover, two additional cell-inspired mechanisms have been considered in the framework of tissue P systems: cell division [8] and cell separation [4]. In the first case, the two new cells created during the cell division process contain exactly the same objects except for at most a pair of different objects, thus cell division produces replication of objects between two new cells. Cell separation is biologically justified by the phenomenon of cell fission: a cell is divided into two new cells such that the contents of the initial cell is distributed between two new cells. A class of tissue P systems with cell separation was presented in [5] and its computational efficiency was investigated in [5] and [10]. In this paper we study the efficiency of tissue P systems with cell separation such that either only the use of symport rules or only the use of antiport rules is allowed. That is, we analyze the relevance of the direction in the application of communication rules allowed in tissue P systems with cell separation, from a computational complexity point of view. The paper is organized as follows: first, we recall some preliminaries, and then, the definition of tissue P systems with cell separation is given. Next, recognizer tissue P systems are briefly described and polynomial complexity classes associated with this kind of systems are introduced. Sections 3 and 4 are devoted to study properties of tissue P systems with cell separation and symport rules, and to analyze their efficiency, yielding the main result of the paper. Finally, conclusions and open problems are presented in the last section. 2. Preliminaries An alphabet Γ is a non–empty set whose elements are called symbols. An ordered finite sequence of symbols of Γ is a string or word over Γ. As usual, the empty string (with length 0) will be denoted by λ. The set of all strings over an alphabet Γ is denoted by Γ∗. A language over Γ is a subset of Γ∗. Amultiset mover an alphabet Γ is a pair m= (Γ, f) where f: Γ →Nis a mapping. For each x∈Γ we say that f(x) is the multiplicity of the symbol xin m. If m= (Γ, f) is a multiset then its support is defined as supp(m) = {x∈Γ|f(x)>0}. A multiset is finite if its support is a finite set. A set is a multiset such that the multiplicity of each element of its support, is equal to 1. If m= (Γ, f) is a finite multiset over Γ, and supp(m) = {a1,...,ak}then it will be denoted as m=af(a1) 1. . . af(ak) k(here the order is irrelevant), and we say that f(a1) + ···+f(ak) is the cardinal of m, denoted by |m|. The empty multiset is denoted by ∅. We also denote by Mf(Γ) the set of all finite multisets over Γ. Let m1= (Γ, f1) and m2= (Γ, f2) multisets over Γ. Then, •The union of m1and m2, denoted by m1+m2, is the multiset (Γ, g), where g=f1+f2, that is, g(x) = f1(x) + f2(x) for each x∈Γ. The Role of the Direction in Tissue P Systems with Cell Separation 187 •The relative complement of m2in m1, denoted by m1\m2, is the multiset (Γ, g), where g=f1(x)−f2(x) if f1(x)≥f2(x) and g(x) = 0 otherwise. •m1is a submultiset of m2, denoted by m1⊆m2, if f1(x)≤f2(x) for each x∈Γ. Let m= (Γ, f) be a multiset over Γ and let Abe a set. We define the intersection m∩Aas the multiset (Γ, g), where g(x) = f(x) for each x∈Γ∩A, and g(x) = 0 otherwise. 2.1. Tissue P Systems with Cell Separation In formal models of membrane systems with cell separation, the cells are not polarized; the two cells obtained by separation have the same labels as the original cell, and if a cell is separated, its interaction with other cells or with the environment is blocked during the separation process. These assumptions, together with the original abstract concept of a P system [6], and previous models studied in [1, 2] and [4], motivated the following definition: Definition 1 Atissue P system with cell separation and communication rules of degree q≥1 is a tuple Π = (Γ,Γ0,Γ1,E,M1,...,Mq,R, iout), where: 1. Γ is a finite alphabet. 2. {Γ0,Γ1}is a partition of Γ, that is, Γ = Γ0∪Γ1, Γ0,Γ16=∅, Γ0∩Γ1=∅. 3. E ⊆ Γ is a finite alphabet. 4. M1,...,Mqare multisets over Γ. 5. Ris a finite set of rules of the following forms: Communication rules: (i, u/v, j), for i, j ∈ {0,1,...,q}, i 6=j,u, v ∈Mf(Γ), |u|+|v|>0; Separation rules: [a]i→[Γ0]i[Γ1]i, where i∈ {1,...,q},a∈Γ and i6=iout. 6. iout ∈ {0,1,...,q}. A tissue P system with cell separation and communication rules can be viewed as a set of qcells, labeled by 1,...,q such that: (a) M1,...,Mqrepresent the finite multisets of objects (symbols of the working alphabet Γ) 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 represents a distinguished region which will encode the output of the system. We use the term region i(0 ≤i≤q) to refer to cell iin the case 1 ≤i≤qand to refer to the environment in the case i= 0. A communication rule (i, u/v, j) is called an antiport rule if u6=λand v6=λ, otherwise it is a symport rule. This rule formally captures the cases where a number of chemical substances (represented by multisets uand v) pass through a cell at the same time, with the help of each other, either in the same direction (symport) or in opposite directions (antiport). A symport rule (i, u/λ, j) provides a virtual arc from region ito region j. An antiport rule (i, u/v, j) provides two arcs: one from region i 188 L. F. MAC´ıAS, M. A. MART´ıNEZ, M. J. P´ EREZ, A. RISCOS, L. VALENCIA to region jand the other from region jto region i. Thus, every tissue P system has an underlying directed graph whose nodes are the regions of the system and the arcs are obtained from communication rules. A communication rule (i, u/v, j) is applicable to regions i, j if the multiset uis contained in region iand multiset vis contained in region j. When applying a communication rule (i, u/v, j), the objects of the multiset represented by uare sent from region ito region jand, simultaneously, the objects of multiset vare sent from region jto region i. The length of communication rule (i, u/v, j) is defined as |u|+|v|. A separation rule [a]i→[Γ0]i[Γ1]iis applicable to cell iif object ais contained in that cell. When applying a separation rule [a]i→[Γ0]i[Γ1]i, in reaction with an object a, the cell iis separated into two cells with the same label; at the same time, the object ais consumed; the objects from Γ0are placed in the first cell, those from Γ1are placed in the second cell. Note that if there are several copies of a, only one of them is consumed, the rest goes into one of the new cells. The output cell iout cannot be separated. The rules are used in a non-deterministic maximally parallel manner. At each step, all cells which can evolve must evolve in a maximally parallel way: we apply a multiset of rules which is maximal, no further applicable rule can be added. Separation rules impose a restriction: when a cell is separated, the separation rule is the only one which is applied for that cell at that step. Aconfiguration at any instant of a tissue P system 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. The initial configuration is C0= (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 cell separation and communication rules Π. We say that configuration C1yields configuration C2in one transition step, denoted by 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: (a) the first term of the sequence is the initial configuration C0of the system; (b) each non-initial configuration of the sequence is obtained from the previous configuration by applying rules of the system in the manner described above; and (c) if the sequence is finite (called halting computation) then the last term of the sequence is called halting configuration. Only halting computations give a result, which is encoded by the objects present in the output region iout in the halting configuration. If C={Ct}0≤t≤rof Π (r∈N) is a halting computation, then the length of C, denoted by |C|, is r, that is, |C| is the number of non-initial configurations which appear in the finite sequence C. We denote by Ct(i) the multiset of objects over Γ contained in all cells labeled by i(by applying separation rules different cells with the same label can be created) at configuration Ct, and Ct(0) denotes the multiset of objects over Γ \ E contained in the environment at configuration Ct. Finally, we denote by C∗ tthe multiset Ct(0) + Ct(1) + ···+Ct(q). The Role of the Direction in Tissue P Systems with Cell Separation 189 2.2. Recognizer Tissue P Systems with Cell Separation and Communication Rules In order to study the computational efficiency of membrane systems, the notion of recognizer tissue P systems is introduced in [8]. Definition 2 A recognizer tissue P system with cell separation and communication rules of degree q≥1 is a tuple Π = (Γ,Γ0,Γ1,Σ,E,M1,...,Mq,R, iin, iout), where: 1. (Γ,Γ0,Γ1,E,M1,...,Mq,R, iout) is a tissue P system with cell separation and communication rules of degree q≥1 (as defined in the previous section). 2. The working alphabet Γ has two distinguished objects yes and no being, at least, one copy of them present in some initial multisets M1,...,Mq, but none of them are present in E. 3. Σ is an (input) alphabet strictly contained in Γ such that E ⊆ Γ\Σ. 4. M1,...,Mqare multisets over Γ \Σ. 5. iin ∈ {1,...,q}is the input cell, and the output region iout is the environment. 6. All computations halt. 7. 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 input alphabet Σ, the computation of the system Πwith input mstarts from the configuration of the form (M1,...,Miin +m, . . ., Mq;∅), that is, the input multiset mhas been added to the contents of the input cell iin. Therefore, in this kind of systems we have an initial configuration associated with each input multiset mover the input alphabet Σ. We say that a computation Cis an accepting computation (respectively, rejecting computation) if object yes (respectively, object no) appears in the environment associated with the corresponding halting configuration of C. Note that, because of the condition that all computations halt, rules of the type (i, λ/v, 0) with v⊂ E are not allowed for recognizer systems. We denote by TSS (respectively, TSA) the class of recognizer tissue P systems with cell separation and symport rules (respectively, antiport rules). For each natural number k≥1, we denote by TSS(k) (respectively, TSA(k)), the class of recognizer tissue P systems with cell separation and symport rules (respectively, antiport rules) of length at most k. Previous results in the literature concern the classes TSC and TSC(k), of recognizer tissue P systems with cell separation and no restriction on the direction of its communication rules. For the case of recognizer tissue P systems using division rules instead of cell separation rules, the corresponding classes are denoted by TDS,TDA and TDC, respectively. 190 L. F. MAC´ıAS, M. A. MART´ıNEZ, M. J. P´ EREZ, A. RISCOS, L. VALENCIA 2.3. Polynomial Complexity Classes of 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. Next, we define the meaning of “efficient solution” to a decision problem in the framework of tissue P systems. Bearing in mind that tissue P systems are devices with a finite description, a countable family of tissue P systems will be necessary in order to solve (any instance of) a decision problem. Definition 3 We say that a decision problem X= (IX, θX) is solvable in polynomial time by a family Π={Π(n)|n∈N}of recognizer tissue P systems with cell separation and communication rules if the following holds: 1. The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time such that on input 1n, constructs the system Π(n). 2. There exists a pair (cod, s) of polynomial-time computable functions over IX such that: (a) for each instance u∈IX,s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u)); (b) for each n∈N,s−1(n) is a finite set; (c) 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; (d) 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; (e) 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 polynomial time by means of families of systems from R, as defined above. The class PMCRis closed under complement and polynomial–time reductions [9]. 2.4. On Efficiency of Tissue P Systems with Cell Separation It is worth pointing out two important results related to the computational efficiency of tissue P systems with cell separation and communication rules: (a) only tractable problems can be efficiently solved by using families of such tissue P systems with The Role of the Direction in Tissue P Systems with Cell Separation 191 communication rules of length at most 2 ([3]), that is, P=PMCTSC(2); and (b) an efficient solution to the SAT problem has been given by means of a family of such tissue P systems with communication rules of length at most 3 ([10]), hence NP∪co −NP ⊆ PMCTSC(3). Therefore, 3 is an optimal bound on the length of communication rules, with respect to the efficiency of tissue P systems with cell separation and communication rules (assuming that P6=NP). 3. Representation of Tissue P Systems from TSS First, we prove a technical result concerning recognizer tissue P systems with cell separation and symport rules. Lemma 1 Let Π = (Γ,Γ0,Γ1,Σ,E,M1,...,Mq,R, iin, iout)be a recognizer tissue P system of degree q≥1from TSS(k),k≥1. Let M=|M1+···+Mq|. Let C={C0,...,Cr}be a computation of Π. For each t, 0≤t≤r, the following holds: 1. If t < r then C∗ t+1 ∩(Γ \ E)⊆ C∗ t∩(Γ \ E). 2. C∗ t∩(Γ \ E)⊆(M1+···+Mq)∩(Γ \ E), and |C∗ t∩(Γ \ E)| ≤ M. 3. |C∗ 0|=Mand |C∗ t+1| ≤ |C∗ t|+M·k, for each t < r. 4. |C∗ t| ≤ M·(1 + k·t). 5. The total number of objects handled by the system along the computation C (including objects from Γ\ E in the environment) is C∗ 0+C∗ 1+···+C∗ r≤M·(1 + r)·(1 + k·r 2) 6. The number of created cells along the computation Cby the application of separation rules, is bounded by M·(1 + r)·(2 + k·r). Proof. 1. Let xbe an object of the multiset C∗ t+1 ∩(Γ \ E) = (Ct+1(0) + Ct+1(1) + ···+Ct+1(q)) ∩(Γ \ E). Let us start recalling that separation rules do not replicate objects and do not produce new objects. Then, at the (t+ 1)th transition step there are two possible scenarios: •xhas not been involved on the application of any communication rule, and then x∈ C∗ t∩(Γ \ E). •xhas been involved on a communication rule. In this case, either xcame from the environment, and then x∈ Ct(0) ∩(Γ \ E), or xcame from another cell, and then x∈(Ct(1) + ···+Ct(q)) ∩(Γ \ E). In both cases x∈ C∗ t∩(Γ \ E). The multisets inclusion that we just proved can be strict for some values of t, in case separation rules were applied in that step, thus consuming some objects. 2. By induction on t. For t= 0 the result is trivial because of C∗ 0∩(Γ \ E) = (C0(0) + C0(1) + ···+C0(q)) ∩(Γ \ E) = (M1+···+Mq)∩(Γ \ E) 192 L. F. MAC´ıAS, M. A. MART´ıNEZ, M. J. P´ EREZ, A. RISCOS, L. VALENCIA Let tbe such that t < r and let us assume the result holds for t(inductive hypothesis). Then C∗ t+1 ∩(Γ \ E) (1) ⊆ C∗ t∩(Γ \ E) (i.h.) ⊆(M1+···+Mq)∩(Γ \ E) Thus, |C∗ t∩(Γ \ E)| ≤ |(M1+···+Mq)∩(Γ \ E)| ≤ M. 3. Obviously, |C∗ 0|=|C0(0) + C0(1) + ···+C0(q)|=|M1+···+Mq|=M. Now, let us compute C∗ t+1 =Ct+1(0) + Ct+1(1) + ···+Ct+1(q). First, let us see what is the contribution to C∗ t+1 of multiset Ct(1) + ···+Ct(q). •Some objects from Ct(1) + ···+Ct(q) either do not evolve, or evolve by the application of symport rules between different cells of the system of the type (i, u/λ, j) with u∈ Ct(1) + ···+Ct(q). These objects will pass to Ct+1(1)+ ···+Ct+1(q). •Some objects from Ct(1) + ···+Ct(q) evolve by the application of symport rules of the type (i, u/λ, 0) with u∈ Ct(1) + ···+Ct(q). Only objects from u∩(Γ \ E) will be produced in Ct+1(0). Now, let us see what is the contribution of multiset Ct(0) to C∗ t+1. •Some objects from Ct(0) do not evolve and they directly pass to Ct+1(0). •The remaining objects from Ct(0) will evolve by means of rules of the type (i, λ/v, 0). In this case, string vmust contain some objects from Ct(0) ⊆Γ\ E. Then, the number of new objects that can arrive to cells by the application of these rules is, at most, |Ct(0)| · (k−1). Hence, |C∗ t+1| ≤ |Ct(1) + ···+Ct(q)|+|Ct(0)| · k≤ |C∗ t|+M·k. 4. By induction on t. For t= 0 the result is trivial because of |C∗ 0|=M. Let tbe such that t < r and the result holds for t. Hence, |C∗ t+1|(3) ≤ |C∗ t|+M·k (i.h.) ≤M·(1 + k·t) + M·k=M·(1 + k·(t+ 1)) 5. It suffices to note that C∗ 0+C∗ 1+···+C∗ r≤M+ (M(1 + k)) + ···+ (M(1 + k·r)) = M·(1 + r) + M·k·r(r+1) 2=M·(1 + r)·(1 + k·r 2) 6. Follows from (5) noting that the each application of a separation rule consumes one object and produces two new cells. 2 Let Π = (Γ,Γ0,Γ1,Σ,E,M1,...,Mq,R, iin, iout) be a recognizer tissue P system from TSS(k), k≥1 1. We denote by RSY (respectively, RSP ) the set of symport rules (respectively, separation rules) of Π. We will fix total orders in RSY and RSP . 2. In order to uniquely identify the cells created by the application of a separation rule, we modify the labels of the new cells in the following recursive manner: The Role of the Direction in Tissue P Systems with Cell Separation 193 •The label of a cell will be represented by a pair (i, σ) where 1 ≤i≤q and σ∈ {0,1}∗. At the initial configuration, the labels of the cells are (1, λ),...,(q, λ). •If a separation rule is applied to a cell labeled by (i, σ), then we create two new labels by appending to the string σa symbol 0 or a symbol 1. That is, the new created cells will be labeled by (i, σ0) and (i, σ1), respectively. Cell (i, σ0) will only contain the objects of cell (i, σ) which belong to Γ0, if any, and cell (i, σ1) will only contain the objects of cell (i, σ) which belong to Γ1, if any. •Note that we can consider a lexicographical order over the set of labels of cells in the system along any computation. 3. If cells labeled by (i, σi) and (j, σj) are engaged by a communication rule, then, after the application of the rule, both cells keep their labels. 4. A configuration Ctof Π is characterized by the multisets of objects over Γ contained in each individual cell and the multiset of objects over Γ\E inside the environment. Then, Ctcan be described by a multiset of labeled objects from {(a, i, σ)|a∈Γ∪{λ},1≤i≤q, σ ∈ {0,1}∗}∪{(a, 0)|a∈Γ\E}.If (a, i, σ)∈ Ct then we say that object aand cell labeled by (i, σ) are in configuration Ct. Let us notice that the number of labels σwe need to identify all cells appearing along a computation of a tissue P system from TSS is cubic in the size of the initial configuration of the system and the length of the computation. 5. Let r≡(i, a1···as/λ, j) be a symport rule of Π, where 1 ≤i, j ≤qand 1≤s≤k. If nis a natural number, then we denote by n·LHS(r, (i, σi),(j, σj)) the multiset of objects over Γ in cell (i, σi) consumed by applying ntimes the rule rto cells (i, σi) and (j, σj). That is, n·LHS(r, (i, σi),(j, σj)) is the following multiset of objects (a1, i, σi)n···(as, i, σi)n. We also denote by n·RHS(r, (i, σi),(j, σj)) the multiset of objects produced in cell (j, σj) by applying ntimes the rule rto cells (i, σi) and (j, σj). That is, n·RHS(r, (i, σi),(j, σj)) is the following multiset of objects (a1, j, σj)n···(as, j, σj)n. 6. Let r≡(i, λ/a1···as,0) be a symport rule of Π, where 1 ≤i≤qand 1 ≤s≤k. If nis a natural number, then we denote by n·LHS(r, (i, σi),0) the multiset of objects over Γ \ E in the environment consumed by applying ntimes the rule rinvolving the environment and cell (i, σi). That is, n·LHS(r, (i, σi),0) is the following multiset of objects ((a1,0)n···(as,0)n)∩((Γ \ E)× {0}). We also denote by n·RHS(r, (i, σi),0) the multiset of objects produced in cell (i, σi) by applying ntimes the rule rinvolving the environment and cell (i, σi). That is, n·RHS(r, (i, σi),0) is the following multiset of objects (a1, i, σi)n···(as, i, σi)n. 7. Let r≡(i, a1···as/λ, 0) be a symport rule of Π, where 1 ≤i≤qand 1 ≤s≤k. If nis a natural number, then we denote by n·LHS(r, (i, σi),0) the multiset of objects consumed in cell (i, σi) by applying ntimes the rule rinvolving the environment and cell (i, σi). That is, n·LHS(r, (i, σi),0) is the following multiset of objects (a1, i, σi)n···(as, i, σi)n. We also denote by n·RHS(r, (i, σi),0) the multiset of objects over Γ \ E in the environment produced by applying ntimes