Trading Polarization for Bi-stable Catalysts in P Systems with Active Membranes

Trading Polarization for Bi-stable Catalysts in P Systems with Active Membranes Mario J. P´erez-Jim´enez and Francisco Jos´e Romero-Campero Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {Mario.Perez, Francisco-Jose.Romero}@cs.us.es Abstract. In the last time, several efforts have been made in order to remove polarizations of membranes from P systems with active membranes; the present paper is a contribution in this respect. In order to compensate the loss of power represented by avoiding polarizations, we use bi-stable catalysts. Polarizationless systems with active membranes which use bi-stable catalysts are proven to be computationally complete and able to solve efficiently NP-complete problems. In this paper we present a solution to SAT in linear time. In order to illustrate the presented solution, we also provide a simulation with CLIPS. 1 Introduction In membrane computing, P systems with active membranes are specially suitable to solve efficiently NP-complete problems, because of the fact that they provide membrane division, inspired from cell division. By using this operation, one can create an exponential number of membranes (working space) in linear time; in this way, we trade space for time to solve NP-complete problems (this has been reported for SAT, VALIDITY, Subset Sum, Knapsack, etc.). One important feature of P systems with active membranes is the polarization of membranes; each membrane has an “electrical charge”, positive (+), negative (−) or neutral (0). However, the electrical charges are not very realistic from a biological point of view. Because of this, several efforts are being made in order to remove the polarizations without losing the universality and the efficiency. This paper goes into this direction of research: we remove the polarization of the membranes but on the other hand we use bi-stable catalysts. This variant of P systems with active membranes is proven to be computationally complete and able to solve NP-complete problems like SAT in linear time. The paper is organized as follows: Section 2 introduces bi-stable catalytic P systems with active membranes without charges as generating devices and as recognizer devices. In Section 3 the complexity classes for P systems are briefly recalled. Sections 4, 5, and 6 present a cellular solution in linear time to the SAT problem within the framework of this variant of P systems. In Section 7 the programming language CLIPS is used to exhibit a simulation of the designed solution in order to illustrate how it works. Conclusions are given in Section 8. 2 Bi-stable Catalytic P Systems with Active Membranes Without Polarizations Definition 1. A bi-stable catalytic P system with active membranes and without polarizations is a tuple Π=(Γ,K,H,µ,M1,...,Mp,R), where: 1. p≥1is the initial degree of the system; 2. Γis the alphabet of symbol-objects; 3. Kis a subset of Γ,K⊆Γ, such that if c∈Kthen c∈K(the elements of Kare called bi-stable catalysts); 4. His a finite set of labels for membranes; 5. µis a membrane structure consisting of pmembranes labelled (not necessarily in a one-to-one manner) with elements of H; 6. M1,...,Mpare strings over Γ, describing the initial multisets of objects associated with the regions of µ; 7. Ris a finite set of evolution rules, of the following forms: (a) [a→ω]h, for h∈H,a∈Γ−K, ω ∈(Γ−K)∗. This is an object evolution rule, associated with a membrane labelled with hbut not directly involving the membrane. (b) [ca →cω ]h,[ca →cω ]h,[ca →cω ]h,[ca →cω ]h, for h∈H,c∈K and a∈Γ−K, ω ∈(Γ−K)∗(bi-stable catalytic evolution rules). Such a rule is an object evolution rule involving bi-stable catalysts, associated with a membrane labelled with h but not directly involving the membrane. (c) a[] h→[b]h, for h∈H,a, b ∈Γ−K(“send in” communication rules). An object from the region immediately outside a membrane labelled with h is introduced in this membrane, possibly transformed into another object. (d) [a]h→b[] h, for h∈H,a, b ∈Γ−K(“send out” communication rules). An object is sent out from membrane labelled with hto the region immediately outside, possibly transformed into another object. (e) [a]h→b, for h∈H,a, b ∈Γ−K(dissolving rules). A membrane labelled with his dissolved in reaction with an object. The skin is never dissolved. (f) [a]h→[b]h[c]h, for h∈H,a, b, c ∈Γ−K(division rules for elementary membranes). An elementary membrane can be divided into two membranes with the same label, possibly transforming some objects. Note that, in contrast to [2], the bi-stable catalysts are not always flip-flop-ing from non-barred to barred versions and back, but also rules of the form ca →cw and ¯ca →¯cw are allowed. The case when the catalysts appear only in rules of the form ca →¯cw and ¯ca →cw is called restricted. 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 non deterministic way), but any object which can evolve by one rule of any form, should evolve. •If a membrane is dissolved, its content (multiset and internal membranes) is left free in the surrounding region. •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) and (b), then we suppose that first the evolution rules of types (a) and (b) 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 (c)-(f). 2.1 Bi-stable Catalytic P Systems with Active Membranes Without Polarizations, as Generating Devices As a generating device, the result (output) of a halting configuration of a bistable catalytic P system is the cardinality of the multiset associated with the environment in the last configuration. In these P systems a non halting computation yields no output. Definition 2. We denote by N(Π)the set of all outputs of halting computations with respect to a bi-stable catalytic P system Π. Theorem 1. Restricted bi-stable catalytic P systems with active membranes without polarization, using rules of type (b) and (d), are computationally complete. Proof. Let Lbe a recursively enumerable language. Let Gbe a matrix grammar with appearance checking such that L(G)=L. We can consider that G= (N,{a},S,M,F) is given in Z-binary normal form, in the standard notation. That is, •N=N1∪N2∪{S, Z, },with these three sets mutually disjoint. •The matrices in Mare in one of the following forms: 1. (S→XA),where X∈N1,A∈N2, 2. (X→Y,A →x),where X, Y ∈N1,A∈N2,x∈(N2∪T)∗,|x|≤2, 3. (X→Y,A →),where X∈N1,Y ∈N1∪{Z},A∈N2, 4. (Z→λ). •F={A→|∃m∈M(m=(X→Y,A →)}. Moreover, if the special symbol Zappears in a sentential form w, then we have w=Zw, with w∈(T∪{})∗(that is, no nonterminal from N2is present). •The matrices in Mwill be ordered as follows: m0:(S→XinitAinit),with Xinit ∈N1,A init ∈N2, m1: . . . mk: ⎫ ⎪ ⎬ ⎪ ⎭ (X→α, A →x),with x∈N1,α∈N1∪{λ},A∈N2, mk+1 : . . . mn: ⎫ ⎪ ⎬ ⎪ ⎭ (X→Y,A →). (X→Z, A →),with X,Y ∈N1,A∈N2 mn+1 :(Z→λ) We construct the system Π=(Γ,K,{1},[] 1,M1,R), where: •Γ=N∪K∪{a, }∪{X,X,X|X∈N1}, •K={ci, ci|0≤i≤n}, •M 1={Xinit,A init,E,c 0,c 1,...,c n}, •The set Rconsists of the following rules: (1.) [ciX→ciY]1 [ciA→cix]1 [ciE→ci]1 [c0Y→c0Y]1 [c0Y→c0Y]1 ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎭ for each mi:(X→Y,A →x),with 1 ≤i≤k. These rules simulate the matrices mi, for i=1,...,k. When we have in the skin region a multiset containing Xand there exists in Ma matrix mi:(X→Y,A →x), the rule [ ciX→ciY]1is applicable. In order to simulate the second component of the grammar one of the rules [ c0Y→ c0Y]1,[c0Y→c0Y]1(either c0or c0is present, hence one of these rules can be used) provides a step in which if there exists an object Ain the skin region, then the rule [ ciA→cix]1can be applied; otherwise, if there is no such object, the rule [ ciE→ci]1produces the trap symbol showing that we can not apply this matrix and so this is not a correct derivation. (2.) [ciX→ciY]1 [c0Y→c0Y]1 [c0Y→c0Y]1 [ciA→ci]1 [ciY→ciY]1 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for each mi:(X→Y,A →),with k+1≤i≤n These rules simulate the matrices mi, for i=k+1,...,n. When we have in the skin region a multiset containing Xand there exists in M a matrix mi:(X→Y,A →), the rule [ ciX→ciY]1is applicable. In order to simulate the second component of the grammar, one of the rules [ c0Y→c0Y]1,[ c0Y→c0Y]1provides a step in which if there exists an object Ain the skin region, the rule [ ciA→ci]1is applied; otherwise, if there is no such object, then the rule [ ciY→ciY]1 completes the simulation of this matrix. (3.) [a]1→a[] 1,[c0→c0]1,[c0→c0]1, The first of these two last rules, [a]1→a[] 1, sends out to the environment the object a. In a halting configuration of the system the multiplicity of the object ain the environment represents the length of the word generated by G. If the computation of the system simulates a non terminal derivation in G, then the rules [ c0→c0]1,[c0→c0]1 produce a non halting computation. From the above remarks it is easy to prove that the equality length(L(G)) = N(Π) holds, where length(L(G)) is the length set of the language L(G), that is, length(L(G)) = {|u||u∈L(G)}. In the previous proof we do not actually use the fact that the membranes are active (for instance, we do not use membrane division); otherwise stated, the proof can be easily reformulated in terms of basic transition P systems, and this makes necessary the comparison of Theorem 1 with universality results known for such systems. First, the universality is known for systems with bi-stable catalysts already from [5], where, however, one uses two membranes (see also Theorem 3.4.7 from [2]; our results improves on this point, because we use only one membrane. Then, in [1] it is proven that two catalysts are sufficient to get universality in P systems without polarizations and without priorities, but the systems considered in [1] contain both catalytic and non-catalytic rules. 2.2 Recognizer Bi-stable Catalytic P Systems with Active Membranes Without Polarization Definition 3. AP system with input is a tuple (Π, Σ,iΠ), where ΠisaP system, with working alphabet Γ, with pmembranes labelled 1,...,p, and initial multisets M1,...,Mpassociated with them, Σis an (input) alphabet strictly contained in Γ, the initial multisets are over Γ−Σ, and iΠis the label of a distinguished (input) membrane. The computations of a P system with an input in the form of a multiset m over Σare defined in a natural way; they start from a configuration which is obtained by adding the multiset mto the initial configuration of the system. Definition 4. Let (Π,Σ, iΠ)be a P system with input. Let Γbe the working alphabet of Π,µthe membrane structure and M1,...,Mpthe initial multisets of Π.Letmbe a multiset over Σ. The initial configuration of (Π,Σ,iΠ) with input mis (µ, M1,...,MiΠ∪m,...Mp). In the case of P systems with input and with external output, the concept of computation is introduced in a similar way as for standard P systems – see [2] – but with a small change. We consider that it is not possible to observe the internal processes inside the P system and we can only know if the computation has halted via some distinguished objects sent out of the skin. We can formalize these ideas in the following way. Definition 5. Arecognizer bi-stable catalytic P system is a P system with input, (Π,Σ,iΠ), and with external output such that: 1. Πis a bi-stable catalytic P system. 2. The working alphabet of Πcontains two distinguished objects YES, NO. 3. All its computations halt. 4. If Cis a computation of Π, then either the object YES or the object NO (but not both) is sent to the environment, and only in the last step of the computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object YES (respectively, NO) appears in the environment in the halting configuration of C. In what follows we will deal with recognizer bi-stable P systems with active membranes without polarizations. Let us denote by BAM the class of this variant of recognizer P systems. 3 The Complexity Class PMCF The first results about “solvability” of NP–complete problems in polynomial time (even linear) by cellular computing systems with membranes were obtained using variants of P systems that lack an input membrane. Thus, the constructive proofs of such results need to design one system for each instance of the problem. This drawback can be easily avoided if we consider a P system with input. Then, the same system could solve different instances of the problem, provided that the corresponding input multisets are introduced in the input membrane. Instead of looking for a single system that solves a problem, we prefer designing a family of P systems such that each element decides all the instances of “equivalent size” of the problem. Definition 6. Let Fbe a class of recognizer P systems. We say that a decision problem X=(IX,θ X)is solvable in polynomial time by a family Π= (Π(n))n∈N+, of systems from F, and we denote this by X∈PMCF,ifthe following is true: •The family Πis polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine constructing Π(n)from n∈N+in polynomial time. •There exists a pair (g,h)of polynomial-time computable functions g:L→ n∈N+IΠ(n)and h:L→N+such that for every u∈Lwe have g(u)∈IΠ(h(u)), and −the family Πis polynomially bounded with regard to (X, g, h); that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(h(u)) with input g(u)is halting and, moreover, it performs at most p(|u|)steps; −the family Πis sound with regard to (X,g,h); that is, for each u∈IX,if there exists an accepting computation of Π(h(u)) with input g(u), then θX(u)=1; −the family Πis complete with regard to (X, g,h); that is, for each u∈IX, if θX(u)=1, then every computation of Π(h(u)) with input g(u)is an accepting one. In the above definition we have imposed to every P system Π(n)tobeconfluent, in the following sense: every computation with the same input produces the same output. The class PMCFis closed under polynomial–time reduction and complement, as proven, for instance, in [10]. 4 Solving SAT in Linear Time The SAT problem is the following one: Given a boolean formula in conjunctive normal form (CNF), to determine whether or not it is satisfiable; that is, whether there exits an assignment to its variables on which it evaluates true. We will address the resolution of this problem via a brute force algorithm within the framework of recognizer bi-stable catalytic P systems with active membranes without charges. Our strategy will consist in: •Generation stage: Using membrane division we generate all possible assignments associated with the formula. •Evaluation stage: In each membrane we evaluate the formula on the assignment produced in that membrane. •Checking stage: In each membrane we check wether or not the formula evaluates true on the assignment from that membrane. •Output stage: Send to the environment the right answer according to the previous stage. Let us consider the function ,defined by n, m=((n+m)(n+m+1)/2)+n for ϕ=C1∧···∧Cma propositional formula in CNF and Var(ϕ)={x1,...,x n}. The function ,is polynomial-time computable (it is primitive recursive and bijective from N2onto N). Also, the inverse function of ,is polynomial. The family presented here is Π={(Π(n, m),Σ(n, m),i(n, m)) |(n, m)∈N2}. For each element of the family, the input alphabet is Σ(n, m)={xi,j, xi,j |1≤i≤m, 1≤j≤n}, the input membrane is i(n, m) = 2, and the P system Π(n, m)=(Γ(n, m),K(n, m),{1,2},µ,M1,M2,R) is defined as follows: •Bi-stable catalysts: K(n, m)={tj, tj,f j, fj,s i, si, ans, ans |1≤i≤m, 1≤j≤n}. •Working alphabet: Γ(n, m)=Σ(n, m)∪K(n, m)∪{vj,p j,n j|1≤j≤n} ∪{ci,r i|1≤i≤m}∪{nok|1≤k≤n+m+3} ∪{, yes, Y ES, NO}. •Membrane structure: µ=[ 1[2]2]1(we will say that every membrane with label2isaninternal membrane). •Initial Multisets: M1={no1, ans}, M2={v1,...,v n, t1,...,tn, f1,...,fn, s1,...,sm,c 1}. •The set Rconsists of the following rules: 1. [ vj]2→[pj]2[nj]2,1≤j≤n. The goal of these rules is to generate an internal membrane for each assignment to the variables of the formula. The new membrane where the object pjappears represents the assignment where xj=true and the new membrane where the object njappears represents the assignment where xj=false. 2. [tjpj→tjpj]2 [tjxij →tjri]2 [tjxij →tj]2 ⎫ ⎬ ⎭ for 1 ≤i≤m, 1≤j≤n. The object pjactivates the catalyst tjwhich “erases” the objects xi,j (these objects represent the literals ¬xj), but reacts with the objects xi,j (these objects represent the literals xj) to produce the object ri (this object indicates that the clause number ievaluates true on the assignment associated with the membrane). 3. [fjnj→fjnj]2 [fjxij →fjri]2 [fjxij →fj]2 ⎫ ⎬ ⎭ for 1 ≤i≤m, 1≤j≤n. The object njactivates the catalyst fjwhich “erases” the objects xi,j (these objects represent the literals xj), but reacts with the objects xi,j (these objects represent the literals ¬xj) to produce the object ri(this object indicates that the clause number ievaluates true on the assignment associated with the membrane). 4. [ siri→siri]2,for 1 ≤i≤m, [sici→sici+1 ]2,for 1 ≤i≤m−1, [smcm→smyes ]2. The objects ciare counters which represent the number of clauses that evaluate true on the assignment associated with the internal membrane. So the object ci, for 1 ≤i≤m−1, reacts with the catalyst si, which is activated by the object ri, to produce the object ci+1, and the object cm reacts with the object rmto produce the object yes in order to show that every clause of the formula evaluates true on the assignment associated with the internal membrane. 5. [ yes ]2→yes [] 2, [ans yes →ansY ES ]1, [YES]1→YES[] 1. These rules produce and send the object YES to the environment. 6. [ noi→noi+1 ]1,for 1 ≤i≤n+2m+3, [ans non+2m+4 →ansNO ]1, [NO ]1→NO [] 1. These rules produce and send out the object NO to the environment. Note that the object NO appears one step later than the object YES and that the catalyst ans get barred in the output stage in order to make sure that the system sends out the right answer. 5 An Overview of the Computation First of all we must define a suitable pair (g,h) of polynomial-time computable functions (see Definition 6) associated with the SAT problem. Given a formula ϕ=C1∧...C min CNF such that Var(ϕ)={x1,...,x n}, we define h(ϕ)= n, m(recall the bijection mentioned in the previous section) and g(ϕ)={xij | xj∈Ci}∪{xj|¬xj∈Ci} Next we will informally describe how the recognizer bi-stable catalytic P system Π(h(ϕ)) with input g(ϕ) works. The computation starts with the generation and evaluation stages. These two stages take place in parallel following the rules from group 1 to 3. The generation of membranes is controlled by the objects vj, for 1 ≤j≤n. When an object vjis present in an internal membrane the rule in 1 is applicable and so the system produces two new membranes. In one of these two new membranes the object pjappears encoding that in the assignment associated with that this variant is computationally complete and able to solve efficiently NP- complete problems like SAT. Future projects are to design families of recognizer bi-stable catalytic P systems to solve numerical NP-complete problems like Knapsack and Tripartite Matching and to study the computational power and efficiency of P systems with active membranes without polarizations. CLIPS has been shown to be a convenient programming language for simulating P systems and it was helpful to debug the design and to understand how the P systems from the family Πwork. Acknowledgement This work is supported by the Ministerio de Ciencia y Tecnolog´ıa of Spain, by the Plan Nacional de I+D+I (2000–2003) (TIC2002-04220-C03-01), cofinanced by FEDER funds, and by a FPI fellowship (of the second author) from the University of Seville. References 1. R. Freund, L. Kari, M. Oswald, P. Sosik, Computationally universal P systems without priorities: Two catalysts suffice. Theoretical Computer Sci., to appear. 2. Gh. P˘aun, Membrane Computing. An Introduction, Springer-Verlag, 2002. 3. Gh. P˘aun, Computing with membranes. Journal of computer and Systems Sciences, 61(1), 2000, 108–143. 4. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, P systems with tables of rules. In: Gh. P˘aun, A. RiscosN´u˜nez, A. Romero-Jim´enez, F. Sancho-Caparrini, eds., Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, 2004, 366–380. 5. Gh. P˘aun, S. Yu, On synchronization in P systems. Fundamenta Informaticae, 38, 4 (1999), 397–410. 6. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini, Teor´ıa de la Complejidad en modelos de computacion celular con membranas, Ed. Kronos, Sevilla, 2002. 7. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, Solving the Subset-Sum problem by active membranes. New Generation Computing, in press. 8. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, A linear-time solution for the Knapsack problem using active membranes. Lecture Notes in Computer Science, 2933 (2004) 140–152. 9. M.J. P´erez-Jim´enez, F.J. Romero-Campero, A CLIPS simulator for recognizer P systems with active membranes. In: Gh. P˘aun, A. Riscos-N´u˜nez, A. Romero- Jim´enez, F. Sancho-Caparrini, eds., Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, 2004, 387–413. 10. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini, A polynomial complexity class in P systems using membrane division. In: E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, Gy. Vaszyl, eds., Proceedings of the Fifth International Workshop on Descriptional Complexity of Formal Systems, 2003, 284–294.