Descriptional Complexity of Tissue-Like P Systems with Cell Division

Descriptional Complexity of Tissue-Like P Systems with Cell Division Daniel D´ıaz-Pernil1, Pilar Gallego-Ortiz2,MiguelA.Guti´errez-Naranjo2, Mario J. P´erez-Jim´enez2, and Agust´ın Riscos-N´u˜nez1 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics I [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda, Reina Mercedes s/n, 41012, Sevilla, Spain [email protected], {magutier,marper,ariscosn}@us.es Abstract. In this paper we address the problem of describing the complexity of the evolution of a tissue-like P system with cell division. In the computations of such systems the number of (parallel) steps is not sufficient to evaluate the complexity. Following this consideration, Sevilla Carpets were introduced as a tool to describe the space-time complexity of P systems. Sevilla Carpets have already been used to compare two different solutions of the Subset Sum problem (both designed in the framework of P systems with active membranes) running on the same instance. In this paper we extend the comparison to the framework of tissue-like P systems with cell division. 1 Introduction Comparing two cellular designs that solve the same problem is not an easy task, as there are many ingredients to be taken into account. Moreover, in the case of P systems where the number of membranes increases along the computation, the problem of describing the complexity of the computational process becomes specially hard. The complexity in time (number of parallel cellular steps) of these solutions is polynomial, but it is clear that the time is not the unique variable that we need to consider in order to evaluate the complexity of the process. This fact has been observed previously in the literature of P systems. The first paper related to this issue was [1], where Ciobanu, P˘aun and S¸tef˘anescu presented a new way to describe the complexity of a computation in a P system. The socalled Sevilla Carpet was introduced as an extension of the notion of Szilard language from grammars to the case when several rules are used at the same time. In [4], the problem was revisited, introducing new parameters for the study of the descriptive complexity of P systems. Besides, several examples of a graphical representation were provided, and the utility of these parameters for comparing different solutions to a given problem was discussed. In that paper two different solutions of the Subset Sum problem, running on the same instance, were compared by using these parameters. In this paper we adapt Sevilla Carpets to tissue-like models, in order to describe the complexity of their computations. Note that given two Sevilla Carpets corresponding to P systems from different models designed to solve a decision problem, we can obtain detailed information about two single computations, but this is not enough to compare the efficiency of the two models in general. Nonetheless, the numerical parameters obtained from these two Sevilla Carpets can give us some hints to compare the corresponding designs of solutions to the problem. The paper is organized as follows. In Section 2 we recall the definition of tissue-like P systems with cell division. In Section 3 we revisit the definition of Sevilla Carpets and its associated parameters. Section 4 shows a comparison among two different solutions to the Subset Sum problem in the framework of P systems with active membranes and one solution designed with tissue-like P systems with cell division, all of them running on the same instance. Some final remarks are also provided. 2 Tissue-Like P Systems with Cell Division Tissue-like P systems with cell division is a well-established P system model presented by Gh. P˘aun et al. in [8]. In this section we briefly recall its main features. The biological inspiration for this model is that alive tissues are not static network of cells, since cells are duplicated via mitosis in a natural way. Formally, a tissue-like P system with cell division of degree q≥1 is a tuple of the form Π=(Γ,E,w 1,...,w q,R,i 0), where: 1. Γis a finite alphabet, whose symbols will be called objects. 2. E⊆Γ. 3. w1,...,w qare strings over Γrepresenting the multisets of objects associated with the cells in the initial configuration. 4. Ris a finite set of rules of the following form: (a) Communication rules:(i, u/v, j), for i, j ∈{0,1,2,...,q},i =j,u, v ∈ Γ∗. (b) Division rules:[a]i→[b]i[c]i,wherei∈{1,2,...,q}and a, b, c ∈Γ. 5. i0∈{0,1,2,...,q}. A tissue-like P system with cell division of degree q≥1 can be seen as a set of qcells (each one consisting of an elementary membrane) labelled by 1,2,...,q. We will use 0 to refer to the label of the environment, and i0denotes the output region (which can be the region inside a cell or the environment). The communication rules determine a virtual graph, where the nodes are the cells and the edges indicate if it is possible for pairs of cells to communicate directly. This is a dynamical graph, because new nodes can appear produced by the application of division rules. The strings w1,...,w qdescribe the multisets of objects initially placed 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 arbitrary large amount of copies. 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. The application of this rule means that the objects of the multisets represented by uand vare interchanged between the two cells. Note that either ior jcan be equal to 0 and in this case the objects are interchanged between one cell and the environment. The division rule [a]i→[b]i[c]iis 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 b in the first one and by cin the other one. 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 membrane 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 cannot be communicated in that step. The main features of this model, from the computational point of view, are that cells have no polarizations (the contrary holds in the cell-like model of P systems with active membranes); 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 blocked during the mitosis process. In some sense, this means that while a cell is dividing it closes the communication channels with other cells and with the environment. 2.1 Recognizer Tissue-Like P Systems with Cell Division Complexity classes within Membrane Computing have been usually studied in the framework of decision problems. Let us recall that a decision problem is a pair (IX,θ X)whereIXis 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 for solving NP-complete decision problems, a special class of tissue P systems with cell division is introduced in [8]: recognizer tissue P systems. The key idea of such recognizer systems is the same one as from recognizer P systems with cell-like structure. Recognizer cell-like P systems were introduced in [10] and they are the natural framework to study and solve decision problems within Membrane Computing, since deciding whether an instance of a given problem has an affirmative or negative answer is equivalent to deciding if a string belongs or not to the language associated with the problem. In the literature, recognizer cell-like P systems are associated with P systems with input in a natural way. The data encoding to an instance of the decision problem has to be provided to the P system in order to compute the appropriate answer. This is done by codifying each instance as a multiset placed in an input membrane. The output of the computation (yes or no) is sent to the environment, in the last step of the computation. In this way, cell-like P systems with input and external output are devices which can be seen as black boxes, in the sense that the user provides the data before the computation starts, and then waits outside the P system until it sends to the environment the output in the last step of the computation. A recognizer tissue-like P system with cell division of degree q≥1 is a tuple Π=(Γ,Σ, E,w 1,...,w q,R,i in,i 0) where –(Γ,E,w 1,...,w q,R,i 0) is a tissue-like P system with cell division of degree q≥1 (as defined in the previous section), i0=env and w1,...,w qstrings over Γ\Σ. –The working alphabet Γhas two distinguished objects yes and no,present in at least one copy in some initial multisets w1, ..., wq, but not present in E. –Σis an (input) alphabet strictly contained in Γ. –iin ∈{1,...,q}is the input cell. –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,w 2,...,w iin w,...,w q;E), that is, after adding the multiset w to 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 of the corresponding computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no)appears in the environment associated to 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 recognizer tissue-like 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 (called a polynomial encoding of IXin Π) 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 defined every P system Π(n)tobeconfluent,in the following sense: every computation of a system with the same input multiset must always give the same answer. 3 Sevilla Carpets Sevilla Carpets were presented in [1] as an extension of the Szilard language, which consists of all strings of rule labels describing correct derivations in a given grammar (see e.g., [6,7] or [11]). The Szilard language is usually defined for grammars in the Chomsky hierarchy where only a single rule is used in each derivation step, so a derivation can be represented as the string of the labels of the rules used in the derivation (the labelling is supposed to be one-to-one). Sevilla Carpets are a Szilard-way to describe a computation in a P system. The main difference is that a multiset of rules can be used in each evolution step of a P system. In [1] a bidimensional writing is proposed to describe a computation of a P system. The (Sevilla) Carpet associated with a computation of a P system is a table with the time on the horizontal axis and the rules explicitly mentioned along the vertical axis; then, for each rule, in each step, a piece of information is given. Depending on the amount of information given to describe the evolution, Ciobanu, P˘aun and S¸tef˘anescu propose five variants for the Sevilla Carpets: 1. Specifying in each time unit for each membrane whether at least one rule was used in its region or not; 2. Specifying in each time unit for each rule whether it was used or not; 3. Mentioning in each time unit the number of applications of each rule; this is 0 when the rule is not used and can be arbitrarily large when the rules are dealing with arbitrarily large multisets; 4. We can also distinguish three cases: that a rule cannot be used, that a rule can be used but it is not because of the nondeterministic choice and that a rule is actually used; 5. A further possibility is to assign a cost to each rule, and to multiply the number of times a rule is used with its cost. They also propose two parameters (weight and surface) to study Sevilla Carpets. In [4] two new parameters (height and average weight)wereproposed. 3.1 Parameters for the Descriptive Complexity Manytimeswewillnotbeinterestedonly in the number of cellular steps of the computation, but also in other type of resources required to perform the computation. Specially if we want to implement in silico a P system, we need to be careful with the number of times that a rule is applied, maybe with the number of membranes and/or the number of objects present in a given configuration. In order to describe the complexity of the computation, the following parameters are proposed: –Weight:It is defined in [1] as the sum of all the elements in the carpet, i.e., as the total number of applications of rules along the computation. The application of a rule has a cost and the weight measures the total cost of the computation. – Surface: It is the multiplication of the number of steps by the total number of the rules used by the P system. It can be considered as the potential size of the computation. From a computational point of view we are not only interested on P systems which halt in a small number of steps, but in P systems which use a small amount of resources. The surface measures the resources used in the design of the P system. Graphically, it represents the surface where the Sevilla Carpet lies on. –Height:It is the maximum number of applications of any rule in a step along the computation. Graphically, it represents the highest point reached by the Sevilla Carpet. –AverageWeight:It is calculated by dividing the weight to the surface of the Sevilla Carpet. This concept provides a relation between both parameters which gives an index on how the P system exploits its massive parallelism. 4 Comparing the Solutions In this section we compare three cellular solutions to the Subset Sum problem: Two of them in the framework of P systems with active membranes and the third one in the framework of tissue-like P systems with cell division. The Subset Sum problem is the following one: Given a finite set A,aweight function, w:A→N, and a constant k∈N, determine whether or not there exists a subset B⊆Asuch that w(B)=k. Two uniform families of P systems with active membranes solving the Subset Sum were presented in [4]. A tuple (n, (w1,...,w n),k) is used in all three solutions to represent an instance of the problem, where nstands for the size of A={a1,...,a n}, wi=w(ai), and kis the constant given as input for the problem. All the solutions are based on a brute force algorithm implemented in the framework of P systems with active membranes. The idea of the design can be divided into several stages: –Generation stage: for every subset of A, a membrane is generated via membrane division. –Weight calculation stage: in each membrane the weight of the associated subset is calculated. This stage will take place in parallel with the previous one. –Checking stage: in each membrane it is checked whether or not the weight of its associated subset is exactly k. This stage cannot start in a membrane before the previous ones are over in that membrane. –Output stage: when the previous stage has been completed in all membranes, the system sends out the answer to the environment. The first family can be found in [9]. Let us recall that the instance u= (n, (w1,...,w n),k) is processed by the P system Π1(n, k) with input the multiset xw1 1xw2 2...x wn n. This design depends on the two constants that are given as input in the problem: nand k. It consists of 5n+5k+18 evolution rules, and if an appropriate input multiset is introduced inside membrane ebefore starting the computation, the system will stop and output an answer in 2n+2k+6steps(iftheansweris No)orin2n+2k+5steps(iftheanswerisYes). The second family is inspired by the previous one. Some modifications were made following the design presented in [3]. In this solution the instance u= (n, (w1,...,w n),k) is processed by the P system Π2(n) with input the multiset xw1 1xw2 2...x wn n. The above design depends only on one of the constants that are given as input in the problem: n. It is quite similar to the previous one, the difference lies in the checking stage and the answer stage. In this case we avoid the use of counters that require knowing the constant k. The number of evolution rules is 5n+ 41, and the number of steps of the computation depends on the concrete instance that we need to solve, but it is linearly bounded. For the study of the Sevilla Carpet in tissue-like P systems with cell division we take the computation of one P system of the family presented in [2]. In that paper a uniform family of tissue-like P systems with cell division solving the Subset Sum problem was presented. The Subset Sum problem was solved in a linear time by a family of recognizer tissue-like P systems with cell division. We compare these solutions with the solution described in [2], where the number of rules for a set A={a1,...,a n}of size nis n·log(k+1)+5n+ 2log(k+1)+3log n+26 ∈O(n·log k) and the number of steps is n+log n+ log(k+1)+10iftheanswerisYes,andn+log n+log(k+1)+12ifthe answer is No. 4.1 Descriptive Complexity We present some detailed statistics about the previous designs, trying to compare them on a more general basis than just looking the number of steps that the computation performs. Following this scheme, we present the Sevilla Carpets associated with the computations of the three different solutions to the Subset Sum problem working on the same instance: u=(6,(2,3,4,8,14,5),15). That 0 10 20 30 40 50 60 70 80 90 100 110 120 Rules 0 5 10 15 20 25 30 35 40 45 Steps Fig. 1. Sevilla Carpet for solution 1 is, n=6,k= 15 and the list of weights is w1=2,w 2=3,w 3=4,w 4=8,w 5= 14,w 6=5. The P system Π1(6,15) has 123 evolution rules. The P system Π1(6,15) stops at step 46 and sends an object Yesto the environment. The weight of the Sevilla Carpet (the total number of rule applications along the computation) is 7597. The height of the Sevilla Carpet (the maximal number of times that a rule is applied in one evolution step) is 281 and it is reached at Step 10. The surface of the Sevilla Carpet is 5658. The average weight of the Sevilla Carpet is 1.3427. The P system Π2(6) has 66 evolution rules. The P system Π2(6) stops at step 51 and sends an object Yesto the environment. Cell-like Tissue-like Sol. 1 Sol.2 Sol. 3 Rules 123 66 97 Steps 46 51 24 Surface 5658 3366 2328 Weight 7597 9491 6592 Height 281 281 755 Average Weight 1.3427 2.8197 2.8316 The weight of the Sevilla Carpet is 9491. The height of the Sevilla Carpet is 281 and it is reached at step 10. The surface of the Sevilla Carpet is 3366. The average weight of the Sevilla Carpet is 2.8197. 0 10 20 30 40 50 60 Rules 0 10 20 30 40 50 Steps Fig. 2. Sevilla Carpet for solution 2 0 10 20 30 40 50 60 70 80 90 Rules 0 5 10 15 20 25 Steps Fig. 3. Sevilla Carpet for solution 3 Finally, the solution with tissue-like P systems with cell division has 97 rules and 95 of them are applied in this computation. The P system stops at step 24. The surface of the Sevilla Carpet is 2328 and its weight is 6592. The height is 755 and it is reached at step 18. The average weight of the Sevilla Carpet is 2.8316. The following table shows the parameters of all three solutions: Asfarasthenumberofrulesisconcerned, we can observe that the second solution is the most compact. From a designer point of view, it is interesting