Looking for Simple Common Schemes to Design Recognizer P Systems with Active Membranes That Solve Numerical Decision Problems

Looking for Simple Common Schemes to Design Recognizer P Systems with Active Membranes That Solve Numerical Decision Problems Carmen Graciani-D´ıaz and Agust´ın Riscos-N´u˜nez Dpto. Ciencias de la Computaci´on e Inteligencia Artificial {cgdiaz, ariscosn}@us.es Abstract. Earlier solutions to decision problems by means of P systems used many counter objects to control the synchronization of different stages in a computation (usually as many counters as the stage must last in the worst case). In this paper we propose a way to replace those counters with some spacial objects for each stage. Furthermore, following the ideas presented in [1], in order to have a common scheme to attack numerical problems, all instances of a problem with the same size are solved by the same P system (which depends on the size) given an input which describes the corresponding instance of the problem. We illustrate these ideas with a cellular solution to the Subset-Sum problem. 1 Preliminaries Since the introduction of P systems [3] a great amount of contributions in that field has been reported. In particular, many papers are devoted to solving decision or numerical NP–complete problems in polynomial time. In order to deal with such kind of problems, an exponential size workspace is generated (in the number of objects and the number of membranes). In this paper we deal with decision problems in the framework of P systems. We recall that a decision problem,X, is a pair (IX,θX) such that IXis a language over a finite alphabet whose elements are called instances and θXis a boolean function over IX. For an instance uof the problem X,ifθX(u)=1 (resp. θX(u) = 0) the answer of the problem for that instance is Yes (resp. No). In the general definition, P systems are non-deterministic. Therefore they do not seem to be a suitable tool to solve a decision problem. For that reason a condition that restricts, in a certain way, the non-determinism is demanded. More specifically, we will work with confluent systems (all computations with the same initial configuration produce the same answer). When working with P systems with external output, the user can ignore the inner processes and take only into account the objects that the system expels to the environment. To know when a computation halts, it is demanded that some halting indicator is sent to the environment exactly in the last step. These restrictions make more difficult the design of such systems. Earlier approaches in this area used counter objects to control the synchronization of different stages in a computation. This kind of solutions need, therefore, extra objects and steps that are not necessary to obtain an answer but to control the procedure of obtaining it. In this paper we want to show how this control can be obtained with only a few objects. Furthermore, earlier solutions to NP-complete problems in polynomial time used to design one P system that solves one instance of the problem; therefore the system could not be used to solve any other instance of the problem, even if it was of the same size (see [8,2]). The introduction of P systems with input [6] gave rise to the design of families of systems, each of them able to solve all the instances of the problem of a given size. Another goal of this paper is to present a solution of Subset-Sum problem with schemes of rules more uniform that depend only in the cardinality of the set. The present work is a continuation of [4] and [1]. For this reason we have chosen the same problem and P system model: Subset-Sum problem and recognizer P systems with active membranes, respectively. The solution to Subset-Sum problem will illustrate also how the given schemes can be adapted for the new approach. 1.1 P Systems with Active Membranes For a detailed description of a P system, Π=(Γ,H,µΠ,M1,...,Mp,R), with active membranes, we refer the reader to [2] and [7]. In what follows we briefly describe the rules of the model that will be used in next sections. (a) [la→v] α l(evolution rules), where a∈Γ,v∈Γ∗,α∈{+,−,0},l∈H. Substitutes an object aby a multiset of objects vin a membrane with label land charge α. (b) [la] α l→b[ l]β l(communication rules), where a,b∈Γ,α,β∈{+,−,0} and l∈H. Sends out (to its father) an object afrom a membrane with label land charge αtransformed into the object b. In addition, the charge of the membrane changes to β. (c) a[ l]α l→[lb] β l(communication rules), where a,b∈Γ,α,β∈{+,−,0} and l∈H. An object aenters in a membrane with label land charge α (from its father) transformed into the object b. In addition, the charge of the membrane changes to β. (d) [la] α l→[lb] β l[lc] γ l(division rules), where a,b,c∈Γ,α,β,γ∈{+,−,0} and l∈H. An object adivides a membrane with label land charge αinto two membranes with the same label and charges βand γ. In each of the new membranes the object achanges into objects band c, respectively. This rule can only be applied to elementary membranes and never to the skin. Rules of type (a) are applied as usual in the framework of P systems, that is, in a maximally parallel way. However, only one rule among the remaining types (b)–(d) can be applied to a membrane. The application of the rules is supposed to occur simultaneously (if division must take place in a membrane consider that the objects present in that membrane evolve previously). For a precise definition we refer the reader to [2] and [7]. 1.2 P Systems with Input A variant of P systems arises when considering the possibility of admitting external information before a computation starts. A P system of degree pwith input is a tuple (Π,Σ,iΠ) where: –Πis a P system of degree p. –Σis an input alphabet strictly contained in the work alphabet, Γ. –All the initial multisets are over the alphabet Γ−Σ. –iΠis a label that distinguishes the input membrane. In a P system of degree p, with initial multisets M1,...,Mp, given a multiset of objects mover the input alphabet, the initial configuration with input mis the tuple (µΠ,M1, ..., MiΠ∪m, ..., Mp). Let us denote by IΠthe set of all the possible input multisets. 1.3 P Systems with External Output In this variant the environment collects the output of the computations, instead of an inner membrane. There will be some special objects called halting indicators.APsystem with external output is valid if no computation sends any halting indicator to the environment except in the last step. And that must only occurs if the computation is a halting one. 1.4 Language Recognizer P Systems Alanguage recognizer P system is a P system with input and external output such that the working alphabet contains two halting indicators yes and no.A language recognizer P system is valid and all its computations halt. If the object is yes (resp. no) we say that the computation is an accepting (resp. rejecting) one. We say that {Πn}n∈Nis a family of language recognizer P systems that solves, in polynomial time, a decision problem (IX,θX)if it verifies the following properties: –All the P systems in the family are language recognizers. –There exists a deterministic Turing machine that constructs each member of the family, Πn,fromnin polynomial time. –There exists a polynomial encoding for the set of instances, IX, into the family of P systems, Π(that is, a pair of polynomial time computable functions (cod, s) where cod: IX→n∈NIΠnand s: IX→Nverifying cod(u)∈IΠs(u) for all u∈IX) such that: •A polynomial function, p,existssothatforeachu∈IXall the computations of the system Πs(u)with input cod(u)halt at most in p(|u|) steps. •For each u∈IX, if there exists an accepting computation in the system Πs(u)with input cod(u), then θX(u)=1. It is said then that the family is sound. •For each u∈IX,ifθX(u)=1, then every computation in the system Πs(u)with input cod(u)is an accepting one. It is said then that the family is complete. The resolution of an instance u∈IXby a family of P systems Πconsist of two stages: during the first one (usually called pre-computation stage) we calculate s(u),cod(u)and Πs(u); during the second stage the P system Πs(u)with input cod(u)carries out its computation. 2 A Solution to the Subset-Sum Problem We illustrate the previous discussion with a solution to Subset-Sum problem that can be stated as follows: Given a finite set A={a1,...,an},a weight function ω:A→Nsuch that ω(ai)=ωifor i= 1, ..., n,and a constant k∈N,determine whether or not there exists a subset D⊆Asuch that ω(D)=k. The proposed solution is based on the one given at [4], and is divided into several stages: –Generation stage: Elementary membrane divisions are carried out until obtaining a membrane associated with each subset of A. –Calculating 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 verified if the weight of the associated subset is equal to the constant k. This stage begins in each membrane after the previous ones are over. –Output stage: When the previous stage has been completed in all membranes, the system sends the corresponding answer to the environment and the computation halts. For each n∈N(the cardinality of set A={a1, ..., an}) a P system with active membranes, input and external output is defined as follows: (Πn,Σn,iΠn) where Πn=(Γn,H,µΠ,Ms,Me,n,Mr,Rn), P system of degree. –Working alphabet: Γn={xi|0≤i≤n}∪{#,yes,no,no,q,q0,q1,q2, q3,c,g,g,d,f0,f,f+,b,b,x0,b0,b0,z,z0,z+,z,h0,h1,h1,p,t}. –Set of labels: H={s, e, r}. –Membrane structure: µΠ=[s[e]e[r]r]s. –Initial multisets: Ms=no,Me,n =gf 0dnz0and Mr=h1. –Set of rules: Rnthat consists of the following rules: (a) [ef0]0 e→[eq] − e[ef] + e[ez0→z] 0 e[ez+→z0]0 e [ef+]0 e→[ef0]0 e[ef] + e[ez0→]+ e[ez+]+ e→z[ e]+ e [ef→f+]+ e[ed] + e→#[ e]0 e[ez→z+]+ e The goal of these rules is the generation of one membrane for each subset of A. When an object f0is present in a neutrally charged membrane we pick a new element from Afor its associated subset (summing its weight to the previous ones) and then divide the membrane. In the membranes where q appears no further objects will be added, and the charge of the membrane changes in order to activate the checking stage. The multiplicity of object d controls the number of divisions that must take place. The object zevolves in order to remain only in the last generated membrane, collaborating to control the beginning of the output stage. (b) [exi→xi−1]+ e1≤i≤n [ex0→x0]0 e[ex0→b0]0 e[ex0→]+ e In the beginning, objects xi,1≤i≤n, are introduced encoding the weights of the corresponding elements of A. When the generation stage ends, the multiplicity of object b0will encode the weight of the subset associated with the membrane. (c) [eq→q0]− e[eb0→b0]− e[eb→b] − e These rules mark the beginning of the checking stage in a membrane. Now, the multiplicity of object b0encode the weight of the corresponding subset of Aand the multiplicity of object bencode the value of the constant k. [eg] − e→g[ e]− e Object gwill be used to mark the beginning of the output stage. (d) [eb0]− e→#[ e]+ e[eb] + e→#[ e]− e We compare the number of occurrences of objects b0and bsending them out alternatively. [eq0→q1]− e[eq1→q0]+ e[eq1→q2c] − e [ec] − e→#[ e]+ e[eq2→q3]+ e Objects qiand ccontrol if both objects have been actually sent out or not (if there is an excess or lack of any of them). [eq3]+ e→yes [ e]0 e[eq3]− e→#[ e]0 e[eq0]+ e→#[ e]0 e These rules deal with the different checking results. (e) [sz→zz] 0 sz[ r]0 r→[rz] 0 r[rz→p] 0 r Object zcontrols the beginning of a process in membrane rthat will trigger the output stage. When zappears in membrane s2nobjects gare present in it. [sz] 0 s→#[ s]+ s[sg→g] + sg[ e]0 e→[eg] + e When a membrane ends its checking stage it admits one object g. (f) g[ r]+ r→[rg] − r[rh1→h0]+ r[rh0→h1]− r [rp] − r→p[ r]0 r[rg] 0 r→g[ r]− rp[ r]− r→[rp] + r [rh0]+ r→t[ r]+ r[rh1→h1]+ r We will use membrane rto detect when all objects ghave been admitted in a membrane e. That will mean that the checking stage has finished in all membranes and then, the output stage is triggered. (g) [st] + s→#[ s]− s[syes ]− s→yes [ s]0 s [sno →no ]− s[sno ]− s→no [ s]0 s The presence of object tin membrane sactivates the answering process. If there is any object yes then it must be sent out. Otherwise, an object no goes out. (h) Also, some cleaning can be done during the process. [exi→]− e1≤i≤n[ez→]− e[ed→]− e [eb→]0 e[eb0→]0 e –Input alphabet: Σn={b}∪{xi|1≤i≤n}. –Input membrane: iΠ=e. So we have defined a family of P systems {Πn}n∈N. Each of the members of the family, Πn, solves all the instances of the Subset-Sum problem for a finite set Awith cardinality n. Each instance will be determined by the values of the weight function, ωifor i=1,...,n, and the value of the constant k. The set of possible input multisets is IΠn={bkxω1 1...xωn n|k,ω1, ..., ωn∈N}.Aswe can see, all the members of the family can be constructed by a Turing machine in polynomial time from n. Let us consider IX={(n,(ω1, ..., ωn), k)|n,ω1, ..., ωn,k∈N}(all the instances of the Subset-Sum problem). The pair of functions (cod,s) defined by cod(n,(ω1, ..., ωn), k)=bkxω1 1...xωn nand s(n,(ω1, ..., ωn), k)=nis a polynomial encoding of IXinto {Πn}n∈N. The following data gives us an idea of Πncomplexity: –Size of the working alphabet: n+31∈O(n). –Number of membranes: 3 ∈O(1). –|Ms|+|Me,n|+|Mr|=n+5∈O(n). –Input size: k+ω(A) –Number of rules: 2n+48 –Number of computation steps needed in the worst case: 3n+ 2 min(k,ω(A)) +19 In what follows we will prove that the systems of the family are recognizer P systems that solve the Subset-Sum problem in linear time; that is, that the family is sound, complete, and polynomially bounded. 3 Formal Verification Proposition 1. Consider k,n∈Nand a weight function ω:A→Nsuch that ω(ai)=ωifor i= 1, ..., n. For any l∈Nand i,1≤i≤n,iflis the weight of asubsetD⊆{a1, ..., ai−1}, then from a membrane of the following form [ebk gf +dn−ibl 0xωi 0··· xωn n−i]0 ewe obtain the set of membranes {[ebkq0bl 0]− e|where lis the weight of D∪D’ for ∅ =D’ ⊆{ai, ..., an}} They will be called relevant membranes. The last membrane of this set will be generated after 3(n−i+1) steps. During the process 2n−i+1 −1objects gwill appear in membrane s. Moreover, we also obtain the following set of membranes: {[ebkgf +bl 0]+ e|l=ω(D∪D’)forD’ ⊆{ai, ..., an}} These membranes will be called irrelevant and the last one will be generated after 3(n−i+1)steps. If an abject z+is present in the considered membrane, then it will only remain, as an object z, in the last generated irrelevant membrane. Proof: By decreasing induction on i, starting from i=n. Figure 1 shows the evolution of a membrane [ebkgf +bl 0xωn 0]0 ewhere l is the weight of D⊆{a1, ..., an−1}. The branching represents new generated membranes obtained by division. Fig. 1. Case i=n In node (1) we can see that the relevant membrane [ebkq0bl+ωn 0]− e(where l+ωn=ω(D∪{an})) is obtained after 3 = 3(n−n+ 1) steps. Besides, in the last step 1 = 2n−n+1 −1 object ghas been sent to membrane s. In (2) the irrelevant membrane [ebkgf +bl+ωn 0]+ e(where l+ωnis the weight of D∪{an}) is obtained after 3 = 3(n−n+ 1) steps. In (3) we have obtained the irrelevant membrane [ebkgf +bl 0]+ e, after 2 steps (lis the weight of D=D∪∅). Moreover, Figure 1 shows (underlined) the evolution of an object z+when it is present in the initial membrane and we can see that it only remains, as an object z, in the last obtained irrelevant membrane. Thus, the proposition holds for i=n. Induction step: i+1→i The evolution of [ebkgf +dn−ibl 0xωi 0··· xωn n−i]0 ewhere lis the weight of a subset D⊆{a1, ..., ai−1}is shown in Figure 2. In (1) the relevant membrane [ebkq0bl+ωi 0]− eis obtained. In it l+ωiis the weight of D∪{ai}. In the last step one object gappears in membrane s. In (2), a membrane [ebkgf +dn−(i+1) bl+ωi 0xωi+1 0···xωn n−(i+1) ]0 e,inwhichl is the weight of D∪{ai}⊆{a1, ..., ai}, is obtained. By induction hypothesis, from this membrane we obtain the set of membranes {[ebkq0bl 0]− e|l=ω((D∪{ai})∪D’)for∅ =D’ ⊆{ai+1, ..., an}}.The last member of this set will be generated after 3(n−i)+3=3(n−i+ 1) steps. During this process 2n−i−1 objects gwill appear in membrane s. In addition, the set of irrelevant membranes {[ebkgf +bl 0]+ e|lis the weight of (D∪{ai})∪D’ for D’ ⊆{ai+1, ..., an}} is obtained. The last member of this set will be generated after 3(n−i)+3=3(n−i+ 1) steps. In (3), a membrane [ebkgf +dn−(i+1) bl 0xωi+1 0··· xωn n−(i+1) ]0 ein which lis the weight of Dis obtained. By induction hypothesis, from this membrane the set of relevant membranes {[ebkq0bl 0]− e|l=ω(D∪D’)for∅ =D’ ⊆{ai+1, ..., an}} is generated. The Fig. 2. Induction step i+1→i last member of this set will be generated after 3(n−i)+2=3(n−i+1)−1 steps and during the process 2n−i−1 objects gwill appear in membrane s.From (3), it is also generated the set of irrelevant membranes {[ebkgf +bl 0]+ e|lis the weight of D∪D’ for D’ ⊆{ai+1, ..., an}}. The last member of this set will be generated after 3(n−i)+3=3(n−i+ 1) steps. Thus, from a membrane [ebkgf +dn−ibl 0xωi 0··· xωn n−i]0 ewe will obtain the set of relevant membranes {[ebkq0bl 0]− e|lis the weight of D∪D’ for a subset ∅ =D’ ⊆{ai, ..., an}} (the last member after 3(n−i+ 1) steps). During the process 2(2n−i−1) + 1 = 2n−i+1 −1 objects gappear in membrane s. Besides, we obtain the set of irrelevant membranes {[ebkgf +bl 0]+ e|lis the weight of D∪D’ for D’ ⊆{ai, ..., an}} (the last member after 3(n−i+1) steps). Finally, if an object z+is present in the initial membrane (underlined in Figure 2) it only appears in (2), then by induction hypothesis it will only remain, as an object z, in the last generated irrelevant membrane.  Theorem 2. Given k,n∈Nand a weight function ω:A→N,ω(ai)=ωifor i= 1, ..., nfrom a membrane of the form [ebkgf 0dnxω1 1···xωn nz0]0 ethe set of relevant membranes {[ebkq0bl 0]− e|l=ω(D)forD⊆A}is obtained (last one after 3n+2steps). During the process 2nobjects gappear in membrane s. The set of irrelevant membranes {[ebkgf +bl 0]+ e|l=ω(D)forD⊆A}is also obtained (the last of them after 3n+2steps). The object z0will evolve to an object zthat will only remain in the last generated irrelevant membrane. Proof: Figure 3 shows the evolution of [ebkgf 0dnxω1 1··· xωn nz0]0 e. In (1) the relevant membrane [ebkq0]− eis obtained and during the process an object gappears in membrane s. Fig. 3. Evolution scheme In (2) we have [ebkgf +dn−1xω1 0··· xωn n−1]0 e,casei=1andl=0of proposition 1, and from it we will obtain the set {[ebkq0bl 0]− e|l=ω(D)for ∅ =D⊆A}of relevant membranes (the last one after 3(n−1+1)+2=3n+2 steps) and 2n−1+1 −1=2 n−1 objects gin membrane s. Moreover, from (2) (by Proposition 1) we will also obtain the set of irrelevant membranes {[ebkgf +bl 0]+ e|l=ω(D)forD⊆A}(the last one after 3(n−1+ 1) + 2 = 3n+ 2 steps. Finally, as an object z+appears in (2), from the evolution of z0(again by Proposition 1) it will only remain as an object zin the last generated irrelevant membrane.  Let us see now, given 0 ≤m≤min(k,l), the evolution of a relevant membrane of the form: [eq0bk−mbl−m 0]− e (a) Case: m=k,m=l [eq0]− e⇒[eq1]− e⇒[eq2c] − e⇒#[ eq2]+ e⇒[eq3]+ e⇒yes [ e]0 e (b) Case: m<k,m=l [eq0bk−m]− e⇒[eq1bk−m]− e⇒[eq2cb k−m]− e⇒#[eq2bk−m]+ e⇒ [eq3bk−(m+1) ]− e⇒#[ ebk−(m+1) ]0 e(objects bwill be consumed in the following step). (c) Case: m=k,m<l [eq0bl−m 0]− e⇒#[ eq1bl−(m+1) 0]+ e⇒[eq0bl−(m+1) 0]+ e⇒ #[ ebl−(m+1) 0]0 e(objects b0will be consumed in the following step). (d) Case: m<k,m<l [eq0bk−mbl−m 0]− e⇒#[ eq1bk−mbl−(m+1) 0]+ e⇒ #[ eq0bk−(m+1) bl−(m+1) 0]− e(that will continue evolving as shown) Beginning with m= 0, pairs of objects b0and bare sent out (case (d)) until both of them are finished (case (a)) or a lack of any of them is detected (cases (b) and (c)). At the end, the membrane will be neutrally charged and ready to admit one object g, after that it will remain inactive. The only irrelevant membrane that continues evolving is the one with an object z+that will be sent out (so this object will appear in membrane safter the last object ghas also appeared).