An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division - PDF

Please download to get full document.

View again

of 20
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

News & Politics

Published:

Views: 5 | Pages: 20

Extension: PDF | Download: 0

Share
Related documents
Description
An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division Antonio E. Porreca 1, Niall Murphy 2,3, Mario J. Pérez-Jiménez 4 1 Dipartimento di Informatica, Sistemistica e Comunicazione
Transcript
An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division Antonio E. Porreca 1, Niall Murphy 2,3, Mario J. Pérez-Jiménez 4 1 Dipartimento di Informatica, Sistemistica e Comunicazione Università degli Studi di Milano Bicocca Viale Sarca 336/14, Milano, Italy 2 Departamento de Inteligencia Artificial Universidad Politécnica de Madrid Campus de Montegancedo s/n, Boadilla del Monte, Madrid, Spain 3 CEI Campus Moncloa, UCM-UPM, Madrid, Spain 4 Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, Sevilla, Spain Summary. In the framework of tissue P systems with cell division, the length of communication rules provides a frontier for the tractability of decision problems. On the one hand, the limitation on the efficiency of tissue P systems with cell division and communication rules of length 1 has been established. On the other hand, polynomial time solutions to NP complete problems by using families of tissue P systems with cell division and communication rules of length at most 3 has been provided. In this paper, we improve the previous result by showing that the HAM-CYCLE problem can be solved in polynomial time by a family of tissue P systems with cell division by using communication rules with length at most 2. Hence, a new tractability boundary is given: passing from 1 to 2 amounts to passing from non efficiency to efficiency, assuming that P NP. 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 u and v are strings over Σ, then so is their concatenation uv, obtained by juxtaposition, that is, writing u and v one after the other. The number of symbols in a string u is 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, Σ is the free monoid generated by Σ under the operation of concatenation. Subsets, finite or infinite, of Σ are referred to as languages over Σ. 142 A.E. Porreca, N. Murpy, M.J. Pérez-Jiménez The Parikh vector associated with a string u Σ with respect to alphabet Σ = {a 1,..., a r } is Ψ Σ (u) = ( u a1,..., u ar ), where u ai denotes the number of ocurrences of symbol a i in 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 = {a i1,..., a is } Σ, then we define Ψ Σ1 (u) = ( u ai1,..., u ), ai s for each u Σ. A multiset m over a set A is a pair (A, f) where f : A N is 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 A and supp(m) = {a 1,..., a k }, then it will be denoted as m = {a f(a1) 1,..., a f(a k) k }. That is, superscripts indicate the multiplicity of each element, and if f(x) = 0 for x A, then element x is omitted. A finite multiset m = {a f(a 1) 1,..., a f(a k) k } can also be represented by the string a f(a 1) 1... a f(a k) k over the alphabet {a 1,..., a k }. Nevertheless, all permutations of this string identify the same multiset m precisely. Throughout this paper, we speak about the finite multiset m where m is a string, meaning the finite multiset represented by the string m. If m 1 = (A, f 1 ), m 2 = (A, f 2 ) are multisets over A, then we define the union of m 1 and m 2 as m 1 + m 2 = (A, g), where g = f 1 + f 2, that is, g(a) = f 1 (a) + f 2 (a), for each a A. For any sets A and B the relative complement A \ B of B in A is defined as follows: A \ B = {x A x / B} In what follows, we assume the reader is already familiar with the basic notions and terminology of P systems. For details, see [9]. 2 Introduction Several different models of cell-like P systems have been successfully used to solve computationally hard problems efficiently by trading space for time. An exponential workspace is created in polynomial time by using some kind of rules, and then massive parallelism is used to simultaneously check all the candidate solutions. Inspired by living cells, several ways for obtaining exponential workspace in polynomial time were proposed: membrane division (mitosis) [8], membrane creation (autopoiesis) [4], and membrane separation (membrane fission) [6]. These three ways have given rise to the following models: P systems with active membranes, P systems with membrane creation, and P systems with membrane separation. A new type of P systems, the so-called tissue P systems, was considered in [5]. Instead of considering a hierarchical arrangement, membranes/cells are placed in the nodes of a virtual graph. This variant has two biological justifications: intercellular communication and cooperation between neurons. The common mathematical model of these two mechanisms is a net of processors dealing with symbols An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division 143 and communicating these symbols along channels specified in advance. Communication among cells is based on symport/antiport rules, which were introduced to P systems in [10]. One of the most interesting variants of tissue P systems was presented in [11], where the definition of tissue P systems is combined with aspects of the definition of P systems with active membranes, yielding tissue P systems with cell division. In these models [11], cells may replicate, that is, the two new cells generated by a division rule have exactly the same objects except for at most one differing pair of objects. 2.1 Tissue P Systems with communication rules Definition 2.1 A tissue P system with symport/antiport rules of degree q 1 is a tuple Π = (Γ, E, M 1,..., M q, R, i out ), where: 1. Γ is a finite alphabet. 2. E Γ. 3. M 1,..., M q are strings over Γ. 4. R is a finite set of communication rules of the form (i, u/v, j), for i, j {0, 1, 2,..., q}, i j, u, v Γ, uv i out {0, 1, 2,..., q}. A tissue P system with symport/antiport rules Π = (Γ, E, M 1,..., M q, R, i out ), of degree q 1 can be viewed as a set of q cells, labelled by 1,..., q, with an environment labelled by 0 such that: (a) M 1,..., M q are strings over Γ representing the finite multisets of objects (elements in Γ ) initially placed in the q cells of the system; (b) E is the set of objects located initially in the environment of the system, all of them appearing in an arbitrary number of copies; and (c) i out {0, 1, 2,..., q} represents a distinguished cell or the environment which will encode the output of the system. When applying a rule (i, u/v, j), the objects of the multiset represented by u are sent from region i to region j and, simultaneously, the objects of multiset v are sent from region j to region i. The length of the communication rule (i, u/v, j) is defined as u + v, that is, the total number of objects which appear in the rule. 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 i to 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 j and another one from cell j to cell i. Thus, every tissue P systems 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 their 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 144 A.E. Porreca, N. Murpy, M.J. Pérez-Jiménez 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 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 E have infinite copies in the environment, they are not properly changed along the computation. The initial configuration is (M 1,, M q ; ). A configuration is a halting configuration if no rule of the system is applicable to it. Let us fix a tissue P system with symport/antiport rules Π. We say that configuration C 1 yields configuration C 2 in one transition step, denoted C 1 Π C 2, if we can pass from C 1 to C 2 by applying the rules from R following the previous remarks. A computation of Π is a (finite or infinite) sequence of configurations such that: 1. the first term of the sequence is an 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 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 (a cell or the environment) i out in the halting configuration. Notation: If C = {C i } i r+1 (r N) is a halting computation of Π, 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 C i (j) the contents of cell j at configuration C i. 2.2 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 active membranes [8]. In these models, the An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division 145 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 2.2 A tissue P system with cell division of degree q 1 is a tuple Π = (Γ, E, M 1,..., M q, R, i out ), where: 1. Γ is a finite alphabet. 2. E Γ. 3. M 1,..., M q are strings over Γ. 4. R is 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 i out and a, b, c Γ. 5. i out {0, 1, 2,..., q}. A tissue P system with cell division is a tissue P system with symport/antiport rules where division rules of cells are allowed. When applying a division rule [a] i [b] i [c] i, under the influence of object a, the cell with label i is divided into two cells with the same label; in the first copy, object a is replaced by object b, in the second one, object a is replaced by object c; all the other objects are replicated and copies of them are placed in the two new cells. The output cell i out cannot be divided. The rules of a tissue P systems 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 rule can be added), with the following important remark: if a cell divides, only the division rule is applied to that cell at that step; the objects inside that cell do not evolve by means of communication rules. In other words, we can think that before division a cell interrupts all its communication channels with the other cells and with the environment. The new cells resulting from division will only interact with other cells or with the environment at the next step providing they do not divide once again. The label of a cell identifies the rules which can be applied to it precisely. 2.3 Recognizer Tissue P Systems with Cell Division Let us recall that a decision problem is a pair (I X, θ X ) where I X is a language over a finite alphabet (whose elements are called instances) and θ X is a total boolean function over I X. There are many different ways to describe instances of a decision problem, but we assume that each problem has associated with it a fixed reasonable encoding scheme (in the sense of [2], page 10) which provides a string associated 146 A.E. Porreca, N. Murpy, M.J. Pérez-Jiménez with each problem instance. The size of an instance u I X is the length of the string associated with it by means of a reasonable encoding scheme. 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 over a finite alphabet, can be established as follows. Given a decision problem X = (I X, θ X ), its associated language is L X = {w I X : θ X (w) = 1}. Conversely, given a language L over an alphabet Σ, its associated decision problem is X L = (I XL, θ XL ), where I XL = Σ, 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 by means of languages recognizer devices. In order to study the computational efficiency of membrane systems, the notions from classical computational complexity theory are adapted for Membrane Computing, and a special class of cell-like P systems is introduced in [13]: recognizer P systems (called accepting P systems in a previous paper [12]). Similarly, recognizer tissue P systems are introduced in [11]. Definition 2.3 A recognizer tissue P system with cell division of degree q 1 is a tuple Π = (Γ, Σ, E, M 1,..., M q, R, i in, i out ), where: 1. (Γ, E, M 1,..., M q, R, i out ) is a tissue P system with cell division 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 M 1,..., M q, but none of them are present in E. 3. Σ is an (input) alphabet strictly contained in Γ such that E Σ =. 4. M 1,..., M q are strings over Γ \ Σ. 5. i in {1,..., q} is the input cell. 6. i out = 0, that is, the output region is the environment. 7. All computations halt. 8. If C is 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 m over Σ, the computation of the system Π with input m starts from the configuration of the form (M 1, M 2,..., M iin +m,..., M q ; ), that is, the input multiset m has been added to the contents of the input cell i in. 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 = {C i } i r+1 of Π (r N), we define the result of C as follows: An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division 147 yes, if Ψ {yes,no}(m r,0 ) = (1, 0) Ψ Output(C) = {yes,no}(m i,0 ) = (0, 0) for i = 0,..., r 1 no, if Ψ {yes,no}(m r,0 ) = (0, 1) Ψ {yes,no}(m i,0 ) = (0, 0) for i = 0,..., r 1 where Ψ is the Parikh function, and M i,0 is the multiset over Γ \ E associated with the environment at configuration C i. In particular, M r,0 is the multiset over Γ \ E associated with the environment at the halting configuration C r. We say that a computation C is 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 environment associated with the corresponding halting configuration of C, and neither object yes nor no appears in the environment associated with any non halting configuration of C. For each natural number k 1, we denote by TDC(k) the class of recognizer tissue P systems with cell division and communication rules with length at most k. 2.4 Polynomial Complexity Classes of Tissue P systems with Cell Division Now, we define what it means to solve a decision problem in the framework of tissue P systems efficiently and in a uniform way. Since we define each tissue P system to work on a finite number of inputs, to solve a decision problem we define a numerable family of tissue P systems. Definition 2.4 We say that a decision problem X = (I X, θ X ) is solvable in a uniform way and polynomial time by a family Π = {Π(n) n IN} of recognizer tissue P systems with cell division 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 which constructs the system Π(n) from n IN. 2. There exists a pair (cod, s) of polynomial-time computable functions over I X such that: (a) for each instance u I X, s(u) is a natural number 5 and cod(u) is an input multiset of the system Π(s(u)); (b) for each n IN, 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 I X every 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 I X, if there exists an accepting computation of Π(s(u)) with input cod(u), then θ X (u) = 1; 5 Note, for this definition to be compatible with the notion of uniformity in Boolean circuit complexity [15] we restrict s(u) to be some function on u, the length of u. 148 A.E. Porreca, N. Murpy, M.J. Pérez-Jiménez (e) the family Π is complete with regard to (X, cod, s), that is, for each u I X, 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 R be a class of recognizer tissue P systems. We denote by PMC R the 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 PMC R is closed under complement and polynom
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks