A Prolog Simulator for Deterministic P Systems with Active Membranes

A Prolog Simulator for Deterministic P Systems with Active Membranes A. CORD´ ON-FRANCO, M.A. GUTI´ ERREZ-NARANJO, M.J. P´ EREZ-JIM´ ENEZ, F. SANCHO-CAPARRINI Dpto. de Ciencias de la Computaci´on e Inteligencia Artificial E.T.S. Ingenier´ıa Inform´atica. Universidad de Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Espa˜na {acordon, magutier, marper, fsancho}@us.es Abstract In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in each step of the evolution as literals of an appropriate language of first order logic. We provide a Prolog program to simulate the evolution of these P systems and present some auxiliary tools to simulate the evolution of a P system with active membranes using 2-division which solves the SAT problem following the techniques presented in 10). Keywords Logic programming, Membrane computing, Simulation, Prolog, SAT-problem §1 Introduction In 5), a new model of computation within the framework of Natural Computing was introduced, called P Systems. It is based upon the notion of membrane structure that is used to enclose computing cells in order to make them independent computing units. Also, a membrane serves as a communication channel between a given cell and other cells “adjacent” to it. This model comes from the observation that the processes 2A. Cord´on-Franco et al. which take place in the complex structure of a living cell can be considered as computations. Since these computing devices were introduced several variants have been considered. See 6) for a fairly complete compendium about P systems. The different variants of P systems found in the literature are generally thought as generating devices. Many of them have been proved to be computationally complete 6). The model we study here, P systems with active membranes, works with symbol–objects, and it provides rules for membrane division. In particular, P systems with active membranes are studied in 6), section 7.2. The main goal of this paper is to propose and illustrate a representation of P systems with active membranes based on Logic Programming techniques. The paper is organized as follows: Section 2 briefly presents some ideas about the convenience of using Prolog as the basis for this representation; Section 3 introduces the way to represent all basic ingredients of this model; Section 4 studies the designed algorithm to simulate deterministic P systems with active membranes; Section 5 presents as an example the solution given to SAT problem using this model in 10); Section 6 presents some conclusions and future work about the possibilities of this new simulator and representation techniques using Logic Programming; finally, the Appendix shows a standard work session with the interface provided with the simulator. §2 Why Prolog? Choosing a programming language for an effective implementation of a P system simulator is not an easy decision. The language has to be expressive enough to handle symbolic knowledge in a natural way and the ability of evolving the different configurations following a set of rules. Prolog∗1has both these features. On one hand, the based-tree data structure and the use of infix operators defined ad hoc by the programmer allow us to simulate the natural language and the user can follow the evolution of the system without any knowledge of Prolog (see sections 3.2 and 3.3). On the other hand, Prolog programs are sets of facts and rules and basic mechanisms of Prolog are pattern matching and automatic backtracking, so the design of the inference engine to perform the evolutions has a natural treatment from a programmer point of view. ∗1A good starting point can be 3) or 13). A Prolog Simulator for Deterministic P Systems with Active Membranes 3 Finally, the use of Prolog as programming language has other desirable side effects which are out of the scope of this paper. Prolog fits into all kinds of symbolic reasoning and the use of this representation can be a way to link P systems to other deeply studied fields in Artificial Intelligence. §3 A Logic Programming representation of P systems with active membrane Following 6) aP system with active membranes is a construct: Π = (V, H, µ, w1, . . . , wm, R), where: 1. m≥1, is the initial degree of the system; 2. Vis the alphabet of symbol-objects; 3. His a finite set of labels for membranes; 4. µis a membrane structure, of mmembranes, labelled (not necessarily in a one-to-one manner) with elements of H; 5. w1, . . . , wmare strings over V, describing the initial multisets of objects placed in the mregions of µ; 6. Ris a finite set of evolution rules, of the following forms: a. [hx→u]α h, for h∈H,α∈ {+,−,0},x∈V,u∈V∗. This is an object evolution rule, associated with a membrane labelled with h and depending on the polarity of that membrane, but not directly involving the membrane. b. x[h]α1 h→[hy]α2 h, for h∈H,α1, α2∈ {+,−,0},x, y ∈V. An object from the region immediately outside a membrane labelled with h is introduced in this membrane, possibly transformed into another object, and simultaneously its polarity can be changed. c. [hx]α1 h→[h]α2 hy, for h∈H,α1, α2∈ {+,−,0},x, y ∈V. An object is sent out from membrane labelled with hto the region immediately outside, possibly transformed into another object, and simultaneously the polarity of the membrane can be changed. d. [hx]α h→y, for h∈H,α∈ {+,−,0},x, y ∈V. A membrane labelled with his dissolved in reaction with an object. The skin is never dissolved. e. [hx]α1 h→[hy]α2 h[hz]α3 h, for h∈H,α1, α2, α3∈ {+,−,0},x, y, z ∈V. An elementary membrane can be divided into two membranes with 4A. Cord´on-Franco et al. the same label, possibly transforming some objects and polarity. These rules are applied according to the following principles: •All the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a nondeterministic way), but any object which can evolve by one rule of any form, should evolve. •If a membrane is dissolved, then its content (multiset and internal membranes) is left free in the surrounding region. •All objects and membranes not specified in a rule and which do not evolve remain unchanged to the next step. •If at the same time a membrane his divided by a rule of type (e) and there are objects in this membrane which evolve by means of rules of type (a), then we suppose that first the evolution rules of type (a) are used, and then the division is produced. Of course, this process takes only one step. •The rules associated with membranes labelled with hare used for all copies of this membrane. At one step, a membrane labelled with hcan be the subject of only one rule of types (b)-(e). In order to give a formal representation in Prolog of the basic structures of P systems with active membranes using 2-division, the following representation will be considered. 3.1 Representation of membrane structures A given configuration will be expressed by means of a labelled tree, where: 1. < > is the position to denote the root of the tree and it will be associated to the skin; 2. if < i1, . . . , in>is the position of a membrane h, then < i, i1, . . . , in> will denote the position of the i-th internal membrane to h. There exists one difference between the above representation and the one we use in Prolog: in our Prolog representation, if in one step of the computation a membrane with label < i1, . . . , in>has kinternal membranes, then its children do not have to be labelled with <1, i1, . . . , in>,<2, i1, . . . , in>,. . . ,< k −1, i1, . . . , in>,< k, i1, . . . , in>. This is because if one child membrane is dissolved, the other ones are not re- A Prolog Simulator for Deterministic P Systems with Active Membranes 5 labelled. Besides, new membranes obtained by division are labelled with new indexes, not by filling the holes of previously dissolved membranes. 3.2 Representation of configurations Let us remember that to give a configuration for a P system with active membranes consists in making explicit the membrane structure and the content of every membrane present in this structure. In our model we will represent the configuration in one step of the evolution as a set of one-literal clauses, each of them representing each alive membrane. Hence, in this representation each clause will show the label, position, polarity, multiset of objects and current step of the computation, as well as the P system this membrane belongs to. In this way, the set of clauses gives information about the contents of the membranes and the membrane structure (by means of the position of each one). In a general form, to denote that in the t-th step of its evolution the P system, P, has a membrane at position [pos] with label h, polarity αand mas multiset, we will write P:: hec αat [pos]with mat time t Note that we can use the user-friendly representation of a Prolog literal, instead of the functional representation. In a general way, if m={{x1, . . . , xn}} (with not necessarily xi6=xj), then we will denote m= [x1, . . . , xn]. 3.3 Description of the rules By means of some new function symbols, the rules are also represented as literals. In what follows we present the general form of the different rules showed above: (a) [hx→u]α h Prule xevolves to [u]in hec α (b) x[h]α1 h→[hy]α2 h Prule xout of hec α1sends in yof hec α2 (c) [hx]α1 h→[h]α2 hy Prule xinside of hec α1sends out yof hec α2 (d) [hx]α h→y Prule xinside of hec αdissolves and sends out y 6A. Cord´on-Franco et al. (e) [hx]α1 h→[hy]α2 h[hz]α3 h Prule xinside of hec α1divides into yinside of h ec α2and zinside of hec α3 §4 The algorithm The Prolog algorithm to simulate a P system works in a natural way. The input of the program is the initial configuration of the membranes (which is represented as a set of literals with predicate symbol **, all of them at time 0) and an appropriate set of rules. •Step 1: Initialization. At the beginning, all the membranes are set to applicable and their objects are split into two multiset: one usable multiset, containing all the objects of the initial membrane, and one used multiset which is empty. •Step 2: Transition. If there exists an applicable membrane satisfying the condition of a rule, then the rule is applied in the following way: – (a)-step: At this stage, only rules of type (a) are checked. The object which triggers the rule is removed from the usable and the result multiset by the application of the rule is added to used, to prevent that the same object is used by two different rules at the same step. After the evolution step, the membrane remains to be applicable and new evolution rules can be applied. This stage ends when no more rules of type (a) can be applied. – Non-(a)-step: At this stage, only one rule of the other types (not (a)) can be applied. Let us remember that this simulation only works with deterministic P systems (in fact, it works with confluent ones). The action depends on the kind of rule to apply: ∗Send out rule: The element which triggers the rule is removed from usable multiset and the new one is added to the used multiset of the father membrane. Both membranes changes to not applicable mode. If the element is sent out of the skin, then it is marked with the property outside. ∗Send in rule: It is the reciprocal of the previous one. The element which triggers the rule is removed from usable in the father membrane and the new one is added to the used multiset. Both membranes changes to not applicable mode. ∗Dissolution rule: The element which triggers the rule belongs to A Prolog Simulator for Deterministic P Systems with Active Membranes 7 usable and the new element obtained together with the rest of the elements of the membrane are added to the used multiset of the father membrane. When a membrane mis dissolved, its inner membranes (i.e. its children) become children of the father membrane of min the next stage of evolution. For that, the new positions have to be arranged. The father membrane changes to not applicable mode. ∗Division rule: The element which triggers the rule belongs to usable and the division creates two new membranes in not applicable mode. One of them keeps the original position and the second one gets a position which has not been occupied by any membrane. – End: When no more rules can be applied to applicable membranes, a new configuration (with at time incremented by 1) is stored. In this moment no membrane has applicable or not applicable state. These modes only have validity during the evolution. At this stage, the P system is ready for a new step of the evolution. •Step 3: End of computation. The evolution of the P system finishes when there are no rules to be applied. Notice that due to the features of the implementation, the program only ensures a correct simulation of the evolution for deterministic (confluent) P systems. Nevertheless, most of the usual algorithms that solve interesting problems are covered. §5 A study case: SAT problem 5.1 A linear solution to the SAT problem by P systems with active membranes Propositional Satisfiability is the problem of determining, for a formula of the propositional calculus, if there is an assignment of truth values to its variables for which that formula evaluates to true. By SAT we mean the problem of propositional satisfiability for formulas in conjunctive normal form (CNF). Following 10) we present a family of recognizing P systems with active membranes using 2–division (see 6), section 7.2) solving the SAT problem in linear time. Let us suppose that ϕ=C1∧· · ·∧Cmin CNF and V ar(ϕ) = {x1, . . . , xn}. For each (m, n)∈N2we consider the recognizing P system (Π(hm, ni),Σ(m, n), i(m, n)), 8A. Cord´on-Franco et al. where Σ(m, n) = {xi,j, xi,j : 1 ≤i≤m, 1≤j≤n},i(m, n) = 2 and Π(hn, mi) = (Γ(m, n),{1,2},[1[2]2]1, w1, w2, R) is defined as follows: Γ(m, n) = Σ(m, n)∪ {ck: 1 ≤k≤m+ 2}∪{dk: 1 ≤k≤3n+ 2m+ 3} ∪ {ri,k : 0 ≤i≤m, 1≤k≤2n} ∪ {e, t}∪{Y es, No}. We will say that every internal membrane with label 2 is an internal membrane. The initial content of each membrane is: w1=∅and w2={d1}. The set Rof rules is given by: (a){[2dk]0 2→[2dk]+ 2[2dk]− 2: 1 ≤k≤n}. By using a rule of (a), a membrane with label 2 is divided into two membranes with the same label, but with different polarizations. These rules allow us to duplicate, in one step, the total number of internal membranes. (b){[2xi,1→ri,1]+ 2,[2xi,1→ri,1]− 2: 1 ≤i≤m}, {[2xi,1→λ]− 2,[2xi,1→λ]+ 2: 1 ≤i≤m}. The rules of (b) try to implement a process allowing to the internal membranes to encode the assignment of a variable and, simultaneously, to check the value of all clauses by this assignment, in such a way that if the clause is true, then an object ri,1will appear in the membrane. In other case, the object encoding the variable will disappear. (c){[2xi,j →xi,j−1]+ 2,[2xi,j →xi,j−1]− 2: 1 ≤i≤m, 2≤j≤n}, {[2xi,j →xi,j−1]+ 2,[2xi,j →xi,j−1]− 2: 1 ≤i≤m, 2≤j≤n}. The check process described previously is always made with respect to the first variable appearing in the internal membrane. Hence, the rules of (c) take charge of making a cyclic path through all the variables to get that, initially, the first variable is x1, then x2, and so on. (d){[2dk]+ 2→[2]0 2dk, , [2dk]− 2→[2]0 2dk: 1 ≤k≤n}, {dk[2]0 2→[2dk+1]0 2: 1 ≤k≤n−1}. The rules of (d) are used as controllers of the generating process of the assignments and the encoding of the satisfied clauses: the objects dare sent out to the skin at the same time the checking is made and they come back to the internal membranes to start the division of these membranes. (e){[2ri,k →ri,k+1]0 2: 1 ≤i≤m, 1≤k≤2n−1}. A Prolog Simulator for Deterministic P Systems with Active Membranes 9 The use of objects rin the rules (i), (j) and (k) makes necessary to perform a rotation of these objects. This is the mission of the rules of (e). (f){[1dk→dk+1]0 1:n≤k≤3n−3}; [1d3n−2→d3n−1e0]0 1. Through the counter-objects d, the rules of (f)control the rotation of the elements ri,k in the internal membranes. (g)e[2]0 2→[2c1]+ 2; [1d3n−1→d3n]0 1. The application of the rules of (g) will show that the system is ready to check which clauses are made true by the assignment encoded by an internal membrane. (h){[1dk→dk+1]0 1: 3n≤k≤3n+ 2m+ 2}. The rules of (h) supply counters in the skin through objects d, in such a way that, if objects d3n+2mappear, then they show the end of the checking of the clauses. The objects dk, with 3n+ 2m+ 1 ≤k≤3n+ 2m+ 3, will control the final stage of the computation. (i) [2r1,2n]+ 2→[2]− 2r1,2n. The applicability of the rule (i) encodes the fact that an internal membrane makes true the clause represented by the object r1,2n, through a change in the sign of its polarization. Because of this, we must relabel the values of rrepresenting the different internal membranes. This is done by means of the rules (j). (j){[2ri,2n→ri−1,2n]− 2: 1 ≤i≤m}. (k)r1,2n[2]− 2→[2r0,2n]+ 2. By using the rule (k) the task of making explicit the assignments that make true the clause encoded in that moment of the execution by the object r1,2nis ended. (l){[2ck→ck+1]− 2: 1 ≤k≤m}. The presence of objects ck(with 2 ≤k≤m+ 1) in the internal membranes shows that the assignments making true every clause are being determined. (m) [2cm+1]+ 2→[2]+ 2cm+1. 16 A. Cord´on-Franco et al. 13) Logic Programming: http://www.afm.sbu.ac.uk/logic-prog/ §7 Appendix In what follows we present a sample of the rules written in the format they must be given to the simulator∗3. % Set (a) p1 rule d1 inside_of e2 ec 0 divides_into d1 inside_of e2 ec 1 and d1 inside_of e2 ec-1 ** 1. p1 rule d2 inside_of e2 ec 0 divides_into d2 inside_of e2 ec 1 and d2 inside_of e2 ec-1 ** 2. % Set (b) p1 rule x1_1 evolves_to [r1_1]in e2 ec 1 ** 3. p1 rule z1_1 evolves_to [r1_1]in e2 ec-1 ** 4. ... % Set (c) p1 rule x1_2 evolves_to [x1_1]in e2 ec 1 ** 11. p1 rule x1_2 evolves_to [x1_1]in e2 ec-1 ** 12. p1 rule z1_2 evolves_to [z1_1]in e2 ec 1 ** 13. ... % Set (d) p1 rule d1 inside_of e2 ec 1 sends_out d1 of e2 ec 0 ** 19. p1 rule d1 inside_of e2 ec -1 sends_out d1 of e2 ec 0 ** 20. ... % Set (e) p1 rule r1_1 evolves_to [r1_2] in e2 ec 0 ** 24. p1 rule r1_2 evolves_to [r1_3] in e2 ec 0 ** 25. ... % Set (f) p1 rule d2 evolves_to [d3] in e1 ec 0 ** 30. p1 rule d3 evolves_to [d4] in e1 ec 0 ** 31. p1 rule d4 evolves_to [d5, e] in e1 ec 0 ** 32. % Set (g) p1 rule e out_of e2 ec 0 sends_in c1 into e2 ec 1 ** 33. p1 rule d5 evolves_to[d6]in e1 ec 0 ** 34. % Set (h) ∗3The number after ** is the ordinal associated to the rule. A Prolog Simulator for Deterministic P Systems with Active Membranes 17 p1 rule d6 evolves_to [d7] in e1 ec 0 ** 35. ... p1 rule d12 evolves_to [d13]in e1 ec 0 ** 41. % Set (i) p1 rule r1_4 inside_of e2 ec 1 sends_out r1_4 of e2 ec-1 ** 42. % Set (j) p1 rule r1_4 evolves_to [r0_4] in e2 ec -1 ** 43. p1 rule r2_4 evolves_to [r1_4] in e2 ec -1 ** 44. % Set (k) p1 rule r1_4 out_of e2 ec-1 sends_in r0_4 into e2 ec 1 ** 45. % Set (l) p1 rule c1 evolves_to [c2] in e2 ec -1 ** 46. p1 rule c2 evolves_to [c3] in e2 ec -1 ** 47. % Set (m) p1 rule c3 inside_of e2 ec 1 sends_out c3 of e2 ec 1 ** 48. % Set (n) p1 rule c3 evolves_to [c4, t] in e1 ec 0 ** 49. % Set (o) p1 rule t inside_of e1 ec 0 sends_out t of e1 ec 1 ** 50. % Set (p) p1 rule c4 inside_of e1 ec 1 sends_out yes of e1 ec-1 ** 51. % Set (q) p1 rule d13 inside_of e1 ec 0 sends_out no of e1 ec 1 ** 52.