A Linear Solution for Subset Sum Problem with Tissue P Systems with Cell Division

A Linear Solution for Subset Sum Problem with Tissue P Systems with Cell Division Daniel D´ıaz-Pernil, Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, Agust´ın Riscos-N´u˜nez Research Group on Natural Computing University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain {sbdani,magutier,marper,ariscosn}@us.es Summary. Tissue P systems are a computing model in the framework of Membrane Computing where the tree-like membrane structure is replaced by a general graph. Recently, it has been shown that endowing these P systems with cell division, NP-complete problems can be solved in polynomial time. In this paper we present a solution to the Subset Sum problem via a family of such devices, and we also include the formal verification of such solution. This is the first solution to a numerical NP-complete problem by using tissue P systems with cell division. 1 Introduction Membrane Computing is a bio-inspired computing model based on the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. The devices of this model are generically called P Systems. In the initial definition of the cell-like model of P systems [6], membranes are hierarchically arranged in a tree-like structure. Its biological inspiration comes from the morphology of cells, where small vesicles are surrounded by larger ones. This biological structure can be abstracted into a tree-like graph, where the root represents the skin of the cell (i.e. the outermost membrane) and the leaves represent membranes that do not contain any other membrane (elementary membranes). Besides, two nodes in the graph are connected if they represent two membranes such that one of them contains the other one. Recently, new models of P systems have been explored. One of them is the model of tissue P systems where the tree-like membrane structure is replaced by a general graph. This model has two biological inspirations (see [3, 4]): intercellular communication and cooperation between neurons. The common mathematical model of these two mechanisms is a net of processors dealing with symbols and 114 D. D´ıaz-Pernil et al. communicating these symbols along channels specified in advance. The communication among cells is based on symport/antiport rules, which were introduced as communication rules for P systems in [5]. In symport rules, objects cooperate to traverse a membrane together in the same direction, whereas in the case of antiport rules, objects residing at both sides of the membrane cross it simultaneously but in opposite directions. This paper is devoted to the study of the computational efficiency of tissue P systems with cell division. In literature, different models of cell-like P systems have been successfully used in order to design efficient solutions to NP-complete problems (see, for example, [2] and the references therein). These solutions are obtained by generating an exponential amount of workspace in polynomial time and using parallelism to check simultaneously all the candidate solutions. From the seminal definition of tissue P systems [3, 4], several research lines have been developed and other variants have arisen (see [1] and references therein). One of the most interesting variants of tissue P systems was presented in [8], where the definition of tissue P systems is combined with the one of P systems with active membranes, yielding tissue P systems with cell division. The biological inspiration is clear: alive tissues are not static networks of cells, since cells are duplicated via mitosis in a natural way. One of the main features of such tissue P systems with cell division is related to their computational efficiency. In [8], a polynomialtime solution to the NP-complete problem SAT is shown, and in [1] a linear-time solution for the 3-COL problem was presented. In this paper we go on with the research in this model and present a linear-time solution to another well-known numerical NP-complete problem: the Subset Sum problem. The paper is organized as follows: first we recall some preliminary concepts and the definition of tissue P systems with cell division. Next, recognizing tissue P systems are briefly described. A linear–time solution to the Subset Sum problem is presented in the following section, including a short overview of the computation and the formal verification of the solution. Finally, some conclusions and lines for future research are presented. 2 Preliminaries In this section we briefly recall some of the concepts used later on in the paper. An alphabet,Σ, is a non empty set, whose elements are called symbols. An ordered sequence of symbols is a string. 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 strings of length nbuilt with symbols from the alphabet Σis denoted by Σnand Σ∗=∪n≥0Σn. A language over Σis a subset from Σ∗. 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} and its size is defined as Px∈Af(x). A multiset is empty (resp. finite) if its support is the empty set (resp. finite). Subset Sum with Tissue P Systems with Cell Division 115 A finite multiset m= (A, f) will be denoted as m={{xf(x1) 1, . . . , xf(xk) k}}, where supp(m) = {x1, . . . , xk}, or alternatively as the string xf(x1) 1· · · xf(xk) k. The union of multisets will be denoted as concatenation when using the string notation. In what follows we assume the reader is already familiar with the basic notions and the terminology underlying P systems. For details, see the handbook [7]. 3 Tissue P Systems with Cell Division In the first definition of the model of tissue P systems [3, 4] the membrane structure did not change along the computation. The main features of tissue P systems with cell division, from the computational point of view, are that cells obtained by division have the same labels as the original cell, and if a cell is divided, then its interaction with other cells or with the environment is blocked during the mitosis process. In some sense, this means that while a cell is dividing it closes all its communication channels. This features imply that the underlying graph is dynamic, as nodes can be added during the computation by division and the edges can be deleted/re-established for dividing cells. Actually, the underlying graph of connections between cells will not be handled explicitly: the initial structure is implicitly given by the number of initial cells (nodes) and the communication rules (marking edges that connect nodes); the opening/closing edges will be controlled by the semantics. Formally, a tissue P system with cell division of initial degree q≥1 is a tuple of the form Π= (Γ, w1, . . . , wq,E,R, i0), where: 1. Γis a finite alphabet, whose symbols will be called objects. 2. w1, . . . , wqare strings over Γ. 3. E ⊆ Γ. 4. Ris a finite set of rules of the following form: (a) Communication rules: (i, u/v, j), for i, j ∈ {0,1, . . . , q}, i 6=j,u, v ∈Γ∗. (b) Division rules: [a]i→[b]i[c]i, where i∈ {1,2, . . . , q}and a, b, c ∈Γ. 5. i0∈ {0,1,2, . . . , q}. A tissue P system with cell division of degree q≥1 can be seen as a set of q cells labelled by 1,2, . . . , q. We shall use 0 as the label of the environment, and i0 for the output region (which can be the region inside a cell or the environment). As we said before, the underlying graph expressing connections between cells is implicit, being determined by the communication rules: the nodes are the cells and the edges indicate if it is possible for pairs of cells to communicate directly. The communication rule (i, u/v, j) can be applied over two cells iand jsuch that uis contained in cell iand vis contained in cell j, and neither inor jare being divided. The application of this rule means that the objects of the multisets represented by uand vare interchanged between the two cells. The strings w1, . . . , wqdescribe the multisets of objects placed initially in the qcells of the system. We interpret that E ⊆ Γis the set of objects placed in the environment, each one of them in an arbitrarily large amount of copies. 116 D. D´ıaz-Pernil et al. The division rule [a]i→[b]i[c]ican be applied over a cell icontaining object a. The application of this rule divides this cell into two new cells with the same label. All the objects in the original cell are replicated and copied in each of the new cells, with the exception of the object a, which is replaced by the object bin the first new cell and by cin the second one. Since both new cells keep the same label as their father cell, they keep the same connections too. There is no connection between both new cells. Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way (a universal clock is considered). In one step, each object in a cell can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can participate in a rule of any form must do it, i.e, in each step we apply a maximal set of rules. This way of applying rules has only one restriction: when a cell is divided, the division rule is the only one which is applied for that cell in that step; the objects inside that cell do not move in that step. 4 Recognizing Tissue P Systems with Cell Division NP-completeness has been usually studied in the framework of decision problems. 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. In order to study the computational efficiency, a special class of tissue P systems is introduced in [8]: recognizing1tissue P systems. A recognizing tissue P system with cell division of degree q≥1 is a tuple Π= (Γ, Σ, w1, . . . , wq,E,R, iin, i0), where •(Γ, w1, . . . , wq,E,R, i0) 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, present in at least one copy in an initial multiset w1, . . . , wq, but not present in E. •Σis an (input) alphabet strictly contained in Γ. •iin ∈ {1, . . . , q}is the input cell. •The output region i0is the environment. •All computations halt. •If Cis a computation of Π, then either the object yes or the object no (but not both) must have been released into the environment, and only in the last step of the computation. The computations of the system Πwith input w∈Γ∗start from a configuration of the form (w1, w2, . . . , wiin w, . . . , wq;E), that is, after adding the multiset wto the contents of the input cell iin. We say that the multiset wis recognized by Πif and only if the object yes is sent to the environment, in the last step 1In [8] they were called recognizer tissue P systems. Subset Sum with Tissue P Systems with Cell Division 117 of all its associated computations. We say that Cis an accepting (resp. rejecting) computation if the object yes (resp. no) appears in the environment associated with the corresponding halting configuration of C. Definition 1. We say that a decision problem X= (IX, θX)is solvable in polynomial time by a family Π={Π(n) : n∈N}of recognizing tissue P systems with cell division 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∈N. •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)); −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, moreover, 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. In the above definition we have imposed to every tissue P system Π(n) a confluent condition, in the following sense: every computation of a system with the same input multiset must always give the same answer. The pair of functions (cod, s) are called a polynomial encoding of the problem in the family of P systems. We denote by PMCT D the set of all decision problems which can be solved by means of recognizing tissue P systems with cell division in polynomial time. 5 A Solution for the Subset Sum Problem The Subset Sum problem is the following one: Given a finite set A, a weight function, w:A→N, and a constant k∈N, determine whether or not there exists a subset B⊆Asuch that w(B) = k. Next, we shall prove that the Subset Sum problem can be solved in a linear time by a family of recognizing tissue P systems with cell division. We shall address the resolution via a brute force algorithm. We shall use a tuple (n, (w1, . . . , wn), k) to represent an instance of the problem, where nstands for the size of A={a1, . . . , an},wi=w(ai), and kis the constant given as input for the problem. 118 D. D´ıaz-Pernil et al. Theorem 1. Subset Sum ∈PMCT D. Proof. Let A={a1, . . . , an}be a finite set, w:A→Na weight function, and k∈N. Let g:N×N→Nbe a function defined by g(n, k) = (n+k)(n+k+ 1) 2+n This function is primitive recursive and bijective between N×Nand Nand computable in polynomial time. Let us denote by u= (n, (w1, . . . , wn), k), where wi=w(ai), 1 ≤i≤n, the given instance of the problem. We define the polynomially computable function s(u) = g(n, k). We shall provide a family of tissue P systems where each P system solves all the instances of the Subset Sum problem with the same size. The weight function wof the concrete instance will be provided via an input multiset determined via the function cod(u) = {{vwi i: 1 ≤i≤n}} ∪ {{qk}}. Next, we shall provide a family Π={Π(g(n, k)) : n, k ∈N}of recognizing tissue P systems with cell division which solve the Subset Sum problem in a linear time. For each (n, k)∈N×Nwe shall consider the system Π(g(n, k)) = (Γ, Σ, ω1, ω2,R,E, iin, i0), where •Γ=Σ(n)∪ {Ai, Bi: 1 ≤i≤n} ∪ {zi: 1 ≤i≤n+dlog ne+dlog(k+ 1)e+ 11} ∪ {ci: 1 ≤i≤n+ 1} ∪ {di: 1 ≤i≤ dlog ne+dlog(k+ 1)e+ 4} ∪ {ei: 1 ≤i≤ dlog ne+ 1} ∪ {Bij : 1 ≤i≤n∧1≤j≤ dlog(k+ 1)e+ 1} ∪ {b, f1, g1, g2, p, D, T, S, N, yes,no} •Σ={q}∪{vi: 1 ≤i≤n} •ω1=z1b c1yes no •ω2=DA1· · · An • R is the following set of rules: 1. Division rules: r1,i ≡[Ai]2→[Bi]2[λ]2for i= 1, . . . , n 2. Communication rules: r2,i ≡(1, zi/zi+1,0) for i= 1, . . . , n +dlog ne+dlog(k+ 1)e+ 10 r3,i ≡(1, ci/c2 i+1,0) for i= 1, . . . , n r4≡(1, cn+1/D, 2) r5≡(2, cn+1/d1e1,0) r6,i ≡(2, ei/e2 i+1,0) for i= 1, . . . , dlog ne r7,i ≡(2, di/di+1,0) for i= 1, . . . , dlog ne+dlog(k+ 1)e+ 3 r8,i ≡(2, edlog ne+1Bi/Bi1,0) for i= 1, . . . , n r9,i,j ≡(2, Bij/B2 ij+1,0) for i= 1, . . . , n,j= 1, . . . , dlog(k+ 1)e r10,i ≡(2, Bidlog(k+1)e+1vi/p, 0) for i= 1, . . . , n r11 ≡(2, pq/λ, 0) r12 ≡(2, ddlog ne+dlog(k+1)e+4/g1f1,0) Subset Sum with Tissue P Systems with Cell Division 119 r13 ≡(2, f1p/λ, 0) r14 ≡(2, f1q/λ, 0) r15 ≡(2, g1/g2,0) r16 ≡(2, g2f1/T, 0) r17 ≡(2, T/λ, 1) r18 ≡(1, bT/S, 0) r19 ≡(1, Syes/λ, 0) r20 ≡(1, zn+dlog ne+dlog(k+1)e+11b/N, 0) r21 ≡(1, Nno/λ, 0) • E =Γ− {yes,no} •iin = 2, is the input cell •i0=env, is the output cell The design is structured in the following stages: •Generation Stage: The initial cell labelled by 2 is divided into two new cells; and the divisions are iterated ntimes until a cell has been produced for each possible candidate solution. Simultaneously to this process, two counters (ci and zi) evolve in the cell labelled by 1: the first one controls the step in which the communication between cells 2 and cell 1 starts and the second one will be useful in the output stage. •Pre–checking Stage: When this stage starts, we have 2ncells labelled by 2, each of them encoding a subset of the set A. In each such a cell, as many objects pas the weight of the corresponding subset will be produced. Recall that there are kcopies of the object qin every cell labelled by 2 (since they were introduced as part of the input multiset). •Checking Stage: In each cell labelled by 2, the number of copies of objects p and qare compared. The way to do that is removing from the cell in one step all possible pairs (p, q). After doing so, if some objects por qremain in the cell, then the cell was not encoding a solution of the problem; otherwise, the weight of the subset of Aencoded on the cell equals to kand hence it encodes a solution to the problem. •Output Stage: The system sends to the environment the right answer according to the results of the previous stage: –Answer yes: After the checking stage, there is a cell labelled by 2 without objects pnor q. In this case, such a cell sends an object Tto the cell 1. This object Tcauses the cell 1 to expel an object yes to the environment (see rules r17 –r19). –Answer no: Every cell labelled by 2 contains some objects por q. In this case, no object Tarrives to the cell labelled by 1 and an object no is sent to the environment. The proof will be concluded in Subsection 5.2. Before going on, let us informally present an overview of the computation. 120 D. D´ıaz-Pernil et al. 5.1 An overview of the computation First of all, we recall the polynomial encoding of the Subset Sum problem in the family Πconstructed above. Let u= (n, (w1, . . . , wn), k) be an instance of the problem, s(u) = g(n, k) and cod(u) = {{vwi i: 1 ≤i≤n}} ∪ {{qk}}. Next, we describe informally how the recognizing tissue P system with cell division Π(s(u)) with input cod(u) works. Let us start with the generation stage. Recall that if a division rule is triggered in a cell, then communication rules cannot be simultaneously applied to the contents of such cell. In this stage we have two parallel processes: •On the one hand, in the cell labelled by 1 we have two counters: zi, which will be used in the answer stage, and ci, which will be multiplied until getting 2n copies in exactly nsteps. •On the other hand, in the cells labelled by 2, the division rules are applied. For each object Ai(which codifies a member of the set A) we obtain two cells labelled by 2: one of them has an element Biand the other does not. When all divisions have been done, after nsteps, we shall have 2ncells with label 2 and each of them will contain the encoding of a subset of A. At this moment, the generation stage ends and the pre-checking stage begins. For each cell 2, an object Dis changed by a copy of the counter ci. In this way, 2ncopies of Dwill appear in the cell 1, and in each cell labelled by 2 there will be an object cn+1. The occurrence of such object cn+1 in the cells 2 will produce the apparition of two counters: (a) The counter dilets the checking stage start, since it produces the apparition of the objects g1and f1after dlog ne+dlog(k+ 1)e+ 4 steps. (b) The counter eiwill be multiplied until obtaining 2dlog necopies, ensuring that at least ncopies of edlog ne+1 will be available in the step n+dlog ne+ 2. Then, we trade objects edlog ne+1 and Biagainst Bi1for each element Aiin the subset associated with the cell. After that, for each 1 ≤i≤nwe get 2dlog(k+1)ecopies of Bidlog(k+1)e+1, ensuring that at least k+ 1 copies will be available. Then for each element Ai in the subset associated with the cell we get min{2dlog(k+1)e, w(ai)}copies of object p, in the step n+dlog ne+dlog(k+ 1)e+ 5. The checking takes place in the step n+dlog ne+dlog(k+1)e+6, when all pairs of objects pand qpresent in any cell labelled by 2 are sent to the environment. In this way, if the weight of the subset associated with a cell is equal to k, then no object por qremains in this cell in the next step. Otherwise, if the encoding is not exactly of weight k, then at least one object por qwill remain in the cell. In the next step the answer stage starts. Two cases must be considered for each cell: •If no object por qremain in the cell, the object f1does not evolve, g1evolves to g2, and in the step n+dlog ne+dlog(k+ 1)e+ 8 the objects f1and g2are traded against Tfrom the environment. In the next step Tis sent to the cell 1, Subset Sum with Tissue P Systems with Cell Division 121 and in the step n+dlog ne+dlog(k+ 1)e+ 10, the objects Tand bare sent to the environment traded by S. Finally, in the step n+dlog ne+dlog(k+1)e+11 the objects Sand yes are sent to the environment. •If any object por qremains in the cell, such object is sent to the environment together with the object f1. This causes that the object bstill remains in the cell 2 after the step n+dlog ne+dlog(k+ 1)e+ 10. In this way, the objects b and zn+dlog ne+dlog(k+1)e+11 are traded by the object Nwith the environment, and in the step n+dlog ne+dlog(k+ 1)e+ 12 the objects Nand no are sent to the environment. 5.2 Verification Next, we prove that the family of recognizing tissue P systems with cell division described above solves the Subset Sum problem in a linear time, according to Definition 1. Before going on, let us remark that the defined family is consistent, i.e., all systems of the family are recognizing tissue P systems with cell division. By construction (type of rules and working alphabet) we can check that it is a family of tissue P systems with cell division. Moreover, we shall prove next that all computations of all systems in the family always halt and in the last step of computations either an object yes or no is sent to the environment. Polynomial uniformity of the family Next, we show that the family Π={Π(g(n, k)) : n, k ∈N}defined in Theorem 1 is polynomially uniform by Turing machines. To this aim we are going to show that it is possible to build Π(g(n, k)) in polynomial time with respect to the size of u. It is easy to check that the rules of a system Π(g(n, k)), with n, k ∈Nof the family are defined recursively from the values nand k. Besides, the necessary resources to build an element of the family are of polynomial order with respect to the same: •Size of the alphabet: (n+ 2) · dlog(k+ 1)e+ 6n+ 3dlog ne+ 28 ∈O(n·log k) •Initial number of cells: 2 ∈θ(1). •Initial number of objects: n+ 6 ∈θ(n). •Number of rules: (n+ 2) · dlog(k+ 1)e+ 5n+ 3dlog ne+ 26 ∈O(n·log k) •Maximal length of a rule: 3 ∈θ(1). Therefore, a deterministic Turing machine can build Π(g(n, k)) in a polynomial time with respect to nand k. Notice that every instance u= (n, (w1, . . . , wn), k) is introduced in the initial configuration of its associated cellular system via an input multiset (i.e. an 1-ary representation) and hence, |u| ∈ O(n+k) holds. 128 D. D´ıaz-Pernil et al. Proof. The configuration of item (a) and (b) are obtained by the application of rules r2,n+dlog ne+dlog(k+1)e+9 and r2,n+dlog ne+dlog(k+1)e+10 to the previous configuration. Analogously, the configurations of items (c) and (d) are obtained by the application of rules r20 and r21 respectively. 5.3 Main Results From the discussion in the previous sections and according to the definition of solvability given in Definition 1, we deduce the following result: Theorem 1. Subset Sum ∈PMCT D. As a consequence of this result we have: Theorem 2. NP ∪co −NP ⊆PMCT D. Proof It suffices to make the following observations: the Subset Sum problem is NP-complete, SubsetSum ∈PMCT D and the class PMCT D is stable under polynomial-time reduction, and also closed under complement. 6 Conclusions and Future Work The physical limitations of current silicon-based hardware have been one of the triggers for the development of alternative models of computation (also known as unconventional). In particular, the scientific community is getting increasingly interested on computing models inspired by Nature. These new models abstract features of living entities and use them as inspiration for designing algorithms within new computing paradigms. Membrane Computing is a new cross-disciplinary field of Natural Computing which has reached an important success in its short life. In these years many results have been presented related to the computational power of membrane devices, but up to now no implementation in vivo or in vitro has been carried out. As the classical complexity classes Pand NP are very likely to be different, the design of efficient solutions (in time) to NP-complete problems consequently needs to handle an exponential amount of resources. Cellular Computing with Membranes provides a framework where this trade-off between time and space is formalized in a natural way, getting inspiration from the way new cells are created (are born) from existing ones. Indeed, the mitosis process (cell division) is the motivation for the model of tissue P systems with cell division used in this paper. As the model allows all existing cells to be divided in parallel at every step, it follows directly that one can produce 2nmembranes in nsteps. Using this ability, we have presented in this paper a solution to a numerical NP-complete problem using a family of recognizing tissue P systems with cell division. More precisely, this paper deals with the design and formal verification of an algorithm to solve a well-known problem in an efficient and uniform way, and in Subset Sum with Tissue P Systems with Cell Division 129 this sense it is a theoretical result, mainly related to computational complexity classes. We would like to stress that the result presented in this paper improves previous designs (for other problems) in two senses. On the one hand, the size of the rules is bounded by 3 and, on the other hand, the number of steps and the initial resources are of O(log k) order instead of being linearly dependent on k. This is the first design of a solution to a numerical problem in this framework (up to our knowledge), and thus it may be useful as a template or guidance when addressing other numerical problems. Besides, the strategies that have been applied in the design presented in this paper can be also used when working on similar models. For instance, there is a promising new paradigm within Membrane Computing, namely Spiking Neural P systems, that is based on communication between neurons (recall that the inspiration of tissue P systems comes from communication and cooperation between cells in a tissue). Efficient resolution of hard problems has not yet been addressed in this new model, but it may in a near future. We would also like to mention as future work the development of software tools to simulate such computational processes, as the existing simulators for other membrane computing models have proved to be very useful as assistants for designing P systems and for understanding the way they work. Acknowledgment The authors acknowledge the support of the project TIN2006-13425 of the Ministerio de Educaci´on y Ciencia of Spain, cofinanced by FEDER funds, and the support of the project of excellence TIC-581 of the Junta de Andaluc´ıa. References 1. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A linear–time tissue P system based solution for the 3–coloring problem. Theoretical Computer Science, to appear. 2. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, F.J. Romero-Campero: A linear solution for QSAT with Membrane Creation. In Membrane Computing. International Workshop WMC6, Vienna, Austria, 2005, LNCS 3850, Springer, 2006, 241–252. 3. C. Mart´ın Vide, J. Pazos, Gh. P˘aun, A. Rodr´ıguez Pat´on: A New Class of Symbolic Abstract Neural Nets: Tissue P Systems. In Computing and Combinatorics: 8th Annual International Conference, COCOON 2002, Singapore, 2002, LNCS 2387, Springer, 2002, 290–299. 4. C. Mart´ın Vide, J. Pazos, Gh. P˘aun, A. Rodr´ıguez Pat´on: Tissue P systems. Theoretical Computer Science, 296 (2003), 295–326. 5. A. P˘aun, Gh. P˘aun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295–305. 6. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 7. Gh. P˘aun: Membrane Computing – An Introduction. Springer, Berlin, 2002. 130 D. D´ıaz-Pernil et al. 8. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Tissue P System with cell division. In Second Brainstorming Week on Membrane Computing, Sevilla, Report RGNC 01/2004, (2004), 380–386. 9. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: A polynomial complexity class in P systems using membrane division. In Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, (2003), 284–294.