VisualTissue: A Friendly Tool to Study Tissue P Systems Solutions for Graph Problems

VisualTissue: A Friendly Tool to Study Tissue P Systems Solutions for Graph Problems Rafael Borrego-Ropero, Daniel D´ıaz-Pernil, Juan A. Nepomuceno Escuela T´ecnica Superior de Ingener´ıa Inform´atica Universidad de Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain {rborrego,sbdani,janepo}@us.es Summary. P systems can be classified in two main groups: P systems with the membrane structure described by a tree, and tissue P systems with the membranes placed in the nodes of an arbitrary graph. NP-complete problems have been solved in linear time by trading space for time in the framework of recognizing tissue P systems with cell division. The design of this kind of systems is not an easy task to understand. In this paper we present a software application to help the design of solutions to NP-complete problems in the framework of recognizing tissue P systems with cell division. VisualTissue application can be downloaded from the web: www.visualtissue.es.kz. 1 Introduction Membrane Computing is an emergent branch of Natural Computing introduced by Gh. P˘aun in [9], which, considering as computations the processes that take place into living cells, constructs a new non-deterministic model of computation. In membrane computing there are two types of frameworks: P systems with the membrane structure described by a tree, inspired from the cell, and tissue P systems with the membranes placed in the nodes of an arbitrary graph. The second type corresponds to the idea of forming a network of membranes linked in a specific manner and working together, [10]. In both types, the main idea is having multisets of objects placed in compartments and evolving according to given rules in a synchronous non-deterministic maximally parallel manner. In the last years, this new field has been addressed in different ways: the study of computational properties such as computational power or complexity classes, definition of new variants of membrane systems closer to biological reality, using Membrane Computing as a new framework for performing biological simulations, etc. In the P systems web page [18] several softwares can be found. Most of them are 88 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno thought in order to run an experiment which is built using some kind of membrane system as a simulation framework, for example, for simulating biological systems, as in [14]. On the other hand, another group of software applications are thought as an easy way of visualizing the computations of a P system, [8], that is to say, as a learning tool. In this paper we present a new visual tool called VisualTissue which have been developed in order to help users to understand the computations of tissue P systems with cell division. We have considered the reference [4], which solves 3-col problem in the framework of tissue P systems with cell division. Polynomial solutions to NP-complete problems in Membrane Computing are done by trading time for space, in a theoretical way. Although real implementations of such systems are no possible, because it should be necessary to implement the maximal parallelism in some way, there are very interesting problems to threat in this framework, for example, the P6=NP conjecture [13]. Our tool helps the user to understand the performance of one class of such systems. This paper is organized as follows: in Section 2 tissue P systems with cell division and the 3-col problem are explained, in Section 3 the VisualTissue application software is presented and some of the most important implementation aspects are commented. Finally, ideas for future work are formulated. 2 Tissue P Systems with Cell Division We will give a definition of this model, but first we briefly recall some of the concepts used later. 2.1 Preliminaries 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). If m= (A, f) is a finite multiset over A, then it will be denoted by m= {{a1,...,ak}}, where each element aioccurs f(ai) times, or by a string containing the symbols a1,...,ak. Agraph Gis a pair G= (V, E) where Vis the set of vertices and Eis the set of edges, each one of which is a (unordered) pair of (different) vertices. If {u, v} ∈ E, we say that uis adjacent to v(and also vis adjacent to u). The degree of v∈V is the number of adjacent vertices to v. VisualTissue: A Graphical Simulator of Tissue P Systems 89 In what follows, we assume that the reader is already familiar with the basic notions and terminology underlying P systems. For details, see [10]. 2.2 Tissue P Systems with Cell Division In the first definition of the model of tissue P systems [6, 7] the membrane structure does not change along the computation. Based on the cell-like model of P systems with active membranes, Gh. P˘aun et al. presented in [12] a new model of tissue P systems with cell division. The biological inspiration is clear: alive tissues are not static network of cells, since cells are duplicated via mitosis in a natural way. The main features of this model, from the computational point of view, are that cells are not polarized (the opposite holds in the cell-like model of P systems with active membranes, see [10]); 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. Formally, a tissue P system with cell division of 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 forms: (a) Communication rules: (i, u/v, j), for i, j ∈ {0,1,2,...,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 (each one consisting of an elementary membrane) labeled by 1,2, . . ., q. We shall use 0 to refer to 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, as new nodes can appear produced by the application of division rules. The strings w1,...,wqdescribe the multisets of objects 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 arbitrarily large amount of copies. A 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. 90 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno The division rule [a]i→[b]i[c]ican be applied to 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. Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way. 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 evolve in that step. 2.3 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 computing efficiency for solving NP-complete decision problems, a special class of tissue P systems with cell division is introduced in [12]: recognizing tissue P systems. The key idea of such recognizing system is the same one as from recognizing P systems with a cell-like structure. Recognizing cell-like P systems were introduced in [15] and they are the natural framework to study and solve decision problems within Membrane Computing, since deciding whether an instance 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, recognizing cell-like P systems are associated in a natural way with P systems with input. The data related 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 cell. The output of the computation (yes or no) is sent to the environment. 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 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). VisualTissue: A Graphical Simulator of Tissue P Systems 91 •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. •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 w to the contents of the input cell iin. 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. 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. 2.4 A Solution to the 3–coloring Problem Ak–coloring (k≥1) of an undirected graph G= (V, E) is a function f:V→ {1,...,k}, where the numbers are interpreted as colors. We say that Gis k– colorable if there exists a k–coloring, f, such that f(u)6=f(v) for every edge {u, v} ∈ E(such a k–coloring fis said to be valid). The 3–coloring problem is the following: given an undirected graph G, decide whether or not Gis 3-colorable; that is, if there exists a valid 3–coloring of G. This problem is related to the famous Four Color Conjecture (solved by Appel and Haken [2, 3]). It is a particular case of the colorability problem: Given an undirected graph Gand a number k, decide whether Gis k-coloreable. The NP- completeness of the 3–coloring problem was proved by Stockmeyer [16] (see [5]). First of all we define a polynomial encoding of the 3–coloring problem in a family Πof P systems constructed as in [4]. Let u= (V, E) be an instance of the problem, with nvertices and medges. Then we consider a size mapping on the set of instances defined as s(u) = hn, mi. The codification of the instance will be the multiset cod(u) = {{Aij :{Ai, Aj} ∈ E∧1≤i < j ≤n}} ∪ {{wq}}. The recognizing tissue P system with cell division that was used to solve the 3–coloring problem in [4] is defined as follows. For each n, m ∈N, we consider the system Π(hn, mi) = (Γ(hn, mi), Σ(n), w1, w2(n),R(hn, mi),E(hn, mi), iin, i0) where: •Γ(hn, mi) is the set 92 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno {Ai, Ri, Ti, Bi, Gi, Ri, Bi, Gi: 1 ≤i≤n} ∪ {ai: 1 ≤i≤2n+m+dlog me+ 11} ∪ {ci: 1 ≤i≤2n+ 1} ∪ {di: 1 ≤i≤ dlog me+ 1} ∪ {fi: 2 ≤i≤m+dlog me+ 6} ∪ {Aij , Pij , Pij , Rij , Bij , Gij : 1 ≤i < j ≤n} ∪ {b, D, D, e, T, S, N, [, yes,no} •Σ(n) = {Aij : 1 ≤i < j ≤n} •w1={{a1, b, c1,yes,no}} •w2(n) = {{D, A1,...,An}} • R(hn, mi) is the set of rules: 1. Division rules: r1,i ≡[Ai]2→[Ri]2[Ti]2for i= 1,...,n r2,i ≡[Ti]2→[Bi]2[Gi]2for i= 1,...,n 2. Communication rules: r3,i ≡(1, ai/ai+1,0) for i= 1,...,2n+m+dlog me+ 10 r4,i ≡(1, ci/c2 i+1,0) for i= 1,...,2n r5≡(1, c2n+1/D, 2) r6≡(2, c2n+1/d1D, 0) r7,i ≡(2, di/d2 i+1,0) for i= 1,...,dlog me r8≡(2, D/e f2,0) r9,i ≡(2, fi/fi+1,0) for i= 2,...,m+dlog me+ 5 r10,ij ≡(2, ddlog me+1Aij /Pij ,0) for 1 ≤i < j ≤n r11,ij ≡(2, Pij /Rij Pij ,0) for 1 ≤i < j ≤n r12,ij ≡(2, Pij /Bij Gij ,0) for 1 ≤i < j ≤n r13,ij ≡(2, RiRij /RiRj,0) for 1 ≤i < j ≤n r14,ij ≡(2, BiBij /BiBj,0) for 1 ≤i < j ≤n r15,ij ≡(2, GiGij /GiGj,0) for 1 ≤i < j ≤n r16,j ≡(2, RjRj/[, 0) for 1 ≤j≤n r17,j ≡(2, BjBj/[, 0) for 1 ≤j≤n r18,j ≡(2, GjGj/[, 0) for 1 ≤j≤n r19 ≡(2, e [/λ, 0) r20 ≡(2, e fm+dlog me+6/T, 0) r21 ≡(2, T/λ, 1) r22 ≡(1, b T/S, 0) r23 ≡(1, S yes/λ, 0) r24 ≡(1, b a2n+m+dlog me+11/N, 0) r25 ≡(1, N no/λ, 0) • E(hn, mi) = Γ(hn, mi)− {yes,no} •iin = 2 is the input cell. •i0= 0 is the output region. VisualTissue: A Graphical Simulator of Tissue P Systems 93 3 A Look Inside VisualTissue VisualTissue is a visual software application to understand the design of solutions for NP-complete problems, in the framework of recognizing tissue P system with cell division. Some programming decisions have been taken in order to develop the application. We have chosen C# as programming language because it is a portable and a powerful object-oriented programming language. A great graphical package is available with the language so that C# is a good language for developing a visual tool. The software follows the Model-View-Controller (MVC), an architecture model of software development used in interactive systems. Three different parts or layers can be distinguished: data handling layer, algorithmic or business logic layer, and user interface or graphical layer. With this, it is easier to do maintenance of the code. Rules system Data handling User interface Fig. 1. Model-View-Controller architecture software The application can handle data stored in XML and normal text files, which are compatible with Algraf Project, [19]. XML files can be easily generated and it is the best way to interact with data generated by other programs. Rules of the systems are fixed for the solution of each problem. In a future version, the user will be able to introduce his own tissue P system rules in order to study other possible solutions. The algorithmic layer implements a recognizing tissue P system with cell division. All rules are applied in a non deterministic and maximal parallel way. The design of the tissue P system machine for solving the problem is non-deterministic until the 2nstep. Every computation path reaches the same configuration in 2n steps, and after that the machine is deterministic and confluent. Consequently, we have chosen only a computation path in order to implement the tissue P system in the software, namely the one determined by the lexicographical election of the rules in non-deterministic steps. Other graph problems solutions can be easily added. The graphical layer allows the user a visual and friendly interaction with the application. At the end of the simulation one can see the colored graph result of the problem if the answer is yes. 94 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno Fig. 2. Firstly, the graph to be studied must be drawn. A small screen show us wether it is 3-colorable or not. 3.1 An User Overview of the Application This software tool allows us to follow step by step the execution of tissue P system with membrane division when solving the 3-col problem, [4]. The answers for a specific problem will be yes or no, and the colored graph is provided if it is possible. The user basically can do three different operations to run the system: •Load or draw with the mouse the graph which is going to be studied. Several graphical options are available in the main window. Graphs can be handled in a easy way and images can be saved as image files or pdf files. •Choose tissue 3-col algorithm in order to carry out the simulation. A second screen is showed in which each computation step can be observed. For each step, a graphical situation can be viewed and the different rules applied in each step are written in the bottom of the screen. The picture can be easily handled and each moment of the performance of the algorithm, and can be saved in different images format, or press the buttons with arrows to move between steps. •Choose GO TO option to go directly to a specific step of the system. VisualTissue software is available on the web, at: www.visualtissue.es.kz VisualTissue: A Graphical Simulator of Tissue P Systems 95 Fig. 3. The performance of the tissue P system can be observed step by step. 4 Future Works Future works will be focused on different improvements as, for example: to handle input files of rules, work with other graph problems, consider other kinds of tissue P systems rules such as membrane creation, etc. One of the most interesting future tasks will be to build a software which simulates a Spiking Neural P system, extending this graphical tool. This future software task will be not only a way of visualizing the performance of the system, but also a framework to do simulations with Spiking Neural P systems too. References 1. B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, P. Walter: The Molecular Biology of the Cell. Fourth Edition, Garland Publ. Inc., London, 2002. 2. K. Appel, W. Haken: Every planar map is 4-colorable - 1: Discharging. Illinois Journal of Mathematics, 21 (1977), 429–490. 3. K. Appel, W. Haken: Every planar map is 4-colorable - 2: Reducibility. Illinois Journal of Mathematics, 21 (1977), 491–567. 4. 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.