P Systems with Active Membranes and Two Polarizations

P Systems with Active Membranes and Two Polarizations Artiom ALHAZOV Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T´arraco 1, 43005 Tarragona, Spain E-mail: [email protected] and Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] Rudolf FREUND Faculty of Informatics Vienna University of Technology Favoritenstr. 9, A-1040 Wien, Austria E-mail: [email protected] Gheorghe P˘ AUN Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania and Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected] Abstract. P systems with active membranes using only two electrical charges and only rules of types (a) and (c) assigned to at most two membranes are shown to be computationally complete – thus improving the previous result of this type from the point of view of the number of polarizations as well as with respect to the number of membranes. Allowing a special variant of rules of type (c) to delete symbols by sending them out, even only one membrane is needed. Moreover, we present an algorithm for deterministically deciding SAT in linear time using only two polarizations and global rules of types (a),(c), and (e). 1 Introduction Membrane systems are biologically motivated theoretical models of distributed and parallel computing. The most interesting questions in the area probably are completeness (solving every solvable problem) and efficiency (solving a hard problem in feasible time). In this paper we will address both problems, i.e., we shall show that when using only two polarizations in P systems 20 with active membranes we already obtain computational completeness in only two membranes and as well we shall give an algorithm how to use such systems to decide SAT in linear time. The question of removing the polarizations (charges +,−,0 associated with the membranes) from P systems with active membranes without diminishing their computing power or their efficiency in solving computationally hard problems in a feasible time was formulated several times and was recently considered in various contexts (with the polarizations replaced by various other features, such as label changing – see, e.g., [3], [4]). Here we present another way for improving previous results: the number of polarizations can be decreased to two, without introducing new features. It is worth mentioning that the computational completeness is obtained for systems with the same types of rules as in [15], hence without using membrane division and membrane dissolution, even decreasing the number of membranes from three (Theorem 7.2.1 in [15]) to two. It remains as an open question whether polarizations can be completely removed. There are numerous results of solving such (mostly NP-complete) problems as SAT,HPP, Validity, Subset-Sum, Knapsack, Vertex Cover, Clique, QBF-SAT by P systems with active membranes with three polarizations (e.g., see [3], [4], [1], [2], [8], [9], [11], [12], [13], [14], [16], [17], [19], [20]). The ability of the system to act depending on the membrane polarizations and to change them is a powerful control feature, the use of which is not necessary if one pays the price of changing membrane labels. Another result is solving SAT in a uniform manner, without polarizations and without changing labels, but also using membrane dissolution and non-elementary membrane division. Here we show that two polarizations are enough even when restricting the types of rules to (a),(c),and (e). 2 Prerequisites The reader is assumed to be familiar with basic elements of formal language theory. For an alphabet V, by V∗we denote the free monoid generated by Vunder the operation of concatenation; the empty string is denoted by λ, and V∗\ {λ}is denoted by V+. The family of recursively enumerable languages is denoted by RE;NRE denotes the family of recursively enumerable sets of non-negative integers, and PsRE denotes the family of recursively enumerable sets of Parikh vectors of non-negative integers. In the following we will not distinguish between a vector (y1, ..., yβ),its representation by a multiset or its representation by a string with Parikh vector (y1, ..., yβ).For more notions as well as basic results from the theory of formal languages, the reader is referred to [5] and [18]. We now also recall the definition of a graph-controlled grammar and prove a special normal form needed in the proof of the main theorem stated in this paper: Agraph-controlled grammar is a construct G= (N, T, Lab, S, R, {1},{n}), where Ndenotes the set of non-terminals, Tis the set of terminal symbols, Lab ={1, ..., n}is the set of labels, Sis the start symbol, Ris a finite set of rules that can be represented as a function from Lab to P×2Lab ×2Lab, where Pdenotes the set of all context-free productions over the set Nof non-terminal symbols and the set of terminal symbols T. A rule in Rusually is written in the form (i:p(i), σ (i), ϕ (i)) , where σ(i) is called the success field and ϕ(i) is called the failure field of the rule labelled by i; the context-free production p(i) is of the form A(i)→w(i),where A(i)∈Nand w(i)∈(N∪T)∗. 21 Without loss of generality we not only assume that N∩Lab =∅and that there is only one initial label (i.e., 1) and only one final label (i.e., n, with σ(n) = ϕ(n) = ∅), but we also may assume that if a computation has reached the final label n, then the obtained sentential form is terminal, i.e., it must not contain any non-terminal symbol. As a special technical detail, without loss of generality we may assume any right-hand side w(m) to contain at most one terminal symbol. Finally, again without loss of generality we may also assume that in the case of a string language, the terminal symbols are generated by G exactly in the correct sequence as they form a terminal word. All these features of a normal form for graph-controlled grammars, for example, follow from the constructions and results proved in [6], Theorem 6. We now add one more feature to the normal form of graph-controlled grammars given above, i.e., from such a graph-controlled grammar Gwe now construct a graph-controlled grammar G0=¡N0, T, Lab0, S0, R0,{0},{n+ 1}¢ with N0=N∪ {S0, F}and Lab0=Lab ∪ {0, n + 1, n + 2}, which has the additional feature that all failure fields and all success fields in G0are non-empty: S0and Fare new non-terminal symbols; S0is used as the new start symbol only used in the production assigned to the new label 0, where we take ¡0 : S0→SF, {1},{1}¢; Fis used as a kind of trap symbol which remains for entering an infinite loop at label n+2 with (n+ 2 : F→F, {n+ 2},{n+ 2}). Moreover, if the original final label nwas reached, it was clear that only terminal symbols were present in the current sentential form; hence, to erase the newly added symbol Fwe add the new rule (n:F→λ, {n+ 1},{n+ 1}). Thus, we finish with a terminal word in the new final label n+1,where for sake of conciseness we take (n+ 1 : F→F, {n+ 1},{n+ 1}). In order to obtain all failure fields and all success fields in G0to be non-empty, we construct the set of rules R00 from the set of rules Rin the following way: For every rule (i:p(i), σ (i), ϕ (i)) in Rwe take the rule ¡i:p(i), σ0(i), ϕ (i)0¢,where σ0(i) = σ(i) for σ(i)6=∅and σ0(i) = {n+ 2}for σ(i) = ∅as well as ϕ0(i) = ϕ(i) for ϕ(i)6=∅and ϕ0(i) = {n+ 2}for ϕ(i) = ∅. In sum, we obtain R0=R00 \ {(n:p(n),∅,∅)} ∪ {(0 : S0→SF, {1},{1}),(n:F→λ, {n+ 1},{n+ 1})} ∪ {(n+ 1 : F→F, {n+ 1},{n+ 1}),(n+ 2 : F→F, {n+ 2},{n+ 2})}. We also assume the reader to be familiar with the basic elements of membrane computing, e.g., from [15] (details can be found at http://psystems.disco.unimib.it), in particular, with P systems with active membranes. For the sake of completeness, we recall the definition of P systems with active membranes for the case when only rules of types (a),(b),and (c) or (cλ) as well as possibly (e) are used; 22 in a more general way as in the original definition, we allow the polarizations to be arbitrary non-negative integers. AP system system with active membranes (of degree m≥1) is a construct of the form Π = (O, E, µ, w1, . . . , wm, e1, . . . , em, R), where Ois the alphabet of objects, E={0, ..., n −1}with n≥1 is the set of electrical charges (polarizations), µis the membrane structure (with mmembranes, bijectively labelled with 1,2, . . . , m; by Hwe denote the set of labels {1,2, . . . , m}), w1, . . . , wmare strings over O indicating the multisets of objects at the beginning present in the mregions of µ,e1, . . . , emare the polarizations at the beginning assigned to the membranes 1, . . . , m, and Ris a finite set of rules of the following forms: (a) [a→v]i h, a ∈O, v ∈O∗, h ∈H, i, j ∈E (evolution rules, used in parallel in the region of membrane h, provided that the polarization of the membrane is i); (b) a[ ]i h→[b]j h, a, b ∈O, h ∈H, i, j ∈E (communication rule, sending an object into a membrane, possibly changing the polarization of the membrane); (c) [a]i h→[ ]j hb, a, b ∈O, h ∈H, i, j ∈E (communication rule, sending an object out of a membrane, possibly changing the polarization of the membrane). We shall also consider the following variant of rule type (c): (cλ)[a]i h→[ ]j hb, a ∈O, b ∈O∪ {λ}, h ∈H, i, j ∈E (communication rule, sending an object out of a membrane or “killing” it by sending it through the membrane, possibly changing the polarization of the membrane). (e) [a]i h→[b]j h[c]k h, a, b, c ∈O, h ∈H, i, j, k ∈E (division rules for elementary membranes; in reaction with an object, the membrane is divided into two membranes with the same label, possibly of different polarizations, and the object specified in the rule is replaced in the two new membranes by possibly new objects) Throughout this paper, we shall even use only communication rules [a]i h→[ ]j hbwith a=b or b=λ. The rules of types (b),(c),and (cλ) are considered as involving the membrane, hence, we assume at most one of such a rule to be used for each membrane in a given step; the use of rules is maximally parallel, with the rules chosen in a non-deterministic manner. An output is associated with a halting computation – and only with halting computations – in the form of the objects sent into the environment during the computation; for the following definitions, we assume ∅ D⊆ {a, b, c, cλ, e}: •If we consider only the number of symbols sent out during a halting computation, then the set of all such numbers computed by a system Π is denoted by N(Π). By NOPm(activen, D) we denote the family of all sets N(Π) computed by P systems with at most mmembranes allowing for npolarizations, using rules of the types contained in D. 23 •If we distingish the different symbols sent out during a halting computation, the set of all such vectors of numbers computed by a system Π is denoted by Ps(Π). By PsOPm(activen, D) we denote the family of all sets Ps(Π) computed by P systems with at most mmembranes allowing for npolarizations, using rules of the types contained in D. •If we consider the sequence of symbols sent out during a halting computation and interpret this sequence as a string, then the set of all such strings computed by a system Π is denoted by L(Π). By LOPm(activen, D) we denote the family of all languages L(Π) computed by P systems with at most mmembranes allowing for npolarizations, using rules of the types contained in D. In this paper, we will use only two polarizations, 0 and 1, and this restriction will be indicated by writing active2in the notations defined above. 3 Completeness/Universality with Two Polarizations Stated in the notations of this paper, Theorem 1 from [10] says that PsOP3(active3,{a, b, c}) = PsRE. As announced above, we here not only improve this result with respect to the number of electrical charges (polarizations), but even with respect to the number of membranes, especially when allowing rules of type (cλ) instead of rules (c) : Theorem 3.1 PsOP1(active2,{a, cλ}) = PsRE. Proof. We only prove that any recursively enumerable set of vectors of non-negative integers can be generated by a P system with active membranes using only one membrane, two polarizations, and rules of the types (a) and (cλ). We start with a graph-controlled grammar G0=¡N0, T, Lab0, S0, R0,{0},{n+ 1}¢ which is in the normal form constructed above and represents the given recursively enumerable set Lof Parikh vectors. We now construct a P system with active membranes of degree one Π = (O, {0,1},[1]1,(S, 0) (F, 0) (1,0) ,0, RΠ) using only two polarizations 0 and 1 and rules of the form (a) and (cλ) such that P sP (Π) = L. The simulation of derivations in the graph-controlled grammar G0by derivations in the P system Π uses a colouring technique opening a “window” of length three for the application of the current rule (i:p(i), σ (i), ϕ (i)) to be applied. Basically, the labels k∈Lab occur in the variants (k, l) and the non-terminal symbols B∈N0occur in the variants (B, l),0≤l≤3n. In the following, the label mruns from 1 to n. •As long as membrane 1 (the skin membrane) has polarization 0,the index lof the nonterminal symbols B∈N0in (B, l) may be incremented: [(B, l)→(B, l + 1)]0 1, B ∈N0,0≤l≤3n. •For each m, the index lof m∈Lab in (m, l) is incremented until the index 3m−3 is reached: [(m, l)→(m, l + 1)]0 1,0≤l < 3m−3. 24 •Then we check whether p(m) can be applied to the current contents of membrane 1; by polarizing the membrane we first prohibit the incrementation of the index lin the variables of the form (B, l) : [(m, 3m−3) →(m, 3m−2) E]0 1 In the next step, all objects (B, 3m−2) , B ∈N0,in membrane 1 evolve to (B, 3m−1) , whereas (m, 3m−2) evolves to (m, 3m−1) by applying the following rule: [(m, 3m−2) →(m, 3m−1)]0 1 At the same time, Epasses the skin membrane thereby changing its polarization from 0 to 1 : [E]0 1→[ ]1 1λ •With the polarization of the membrane being 1,the symbols now remain unchanged, only one suitable object – if possible – has to pass the membrane resetting the polarization to 0: [(A(m),3m−1)]1 1→[ ]0 1λ At the same time, the object (m, 3m−1) evolves according to the following rule: [(m, 3m−1) →m0]1 1 •In the next step m0evolves according to the polarization of the skin membrane (the polarization has stored the one-bit information whether A(m) was present or not): If the polarization is still 1,then m0evolves in two further steps to m000, where the symbol Egenerated in the first step then resets the polarization to 0 in the second step by passing the skin membrane: [m0→m00E]1 1, [m00 →m000]1 1, [E]1 1→[ ]0 1λ •As the polarization is 0 again, the symbols (B, 3m−1) , B ∈N0,may evolve to (B, 3m), whereas m0and m000,respectively, evolve to different symbols with index 3m: [m0→( ¯m, 3m)]0 1 [m000 →( ˆm, 3m)]0 1 •The symbols ( ¯m, 3m) and ( ˆm, 3m) until the end of a simulation cycle evolve in the same way as the basic objects (m, l) by incrementing the second parameter: [( ¯m, l)→( ¯m, l + 1)]0 1,3m≤l < 3n; [( ˆm, l)→( ˆm, l + 1)]0 1,3m≤l < 3n. •At the end of a complete cycle, we finally extract the information stored in the symbols ¯mand ˆm, respectively, and start a new cycle: [(B, 3n)→(B, 3n+ 1)]0 1and [(B, 3n+ 1) →(B, 0)]0 1for all B∈N0; [( ˆm, 3n)→( ˆm, 3n+ 1)]0 1or [( ¯m, 3n)→( ¯m, 3n+ 1) h(w(m))]0 1,respectively, where 25 h:N0∪T→(N0,3n+ 1) ∪Tis the morphism with h(B) = (B, 3n+ 1) for all B∈N0and h(a) = afor all a∈T; observe that due to our assumptions about G0, h (w(m)) cannot contain more than one terminal symbol a, which may leave the skin membrane by using the following rule: [a]0 1→[ ]0 1a The next cycle of simulating a derivation in G0by Π starts after the application of one of the following rules: [( ¯m, 3n+ 1) →(k, 0)]0 1for every k∈σ(m)\ {n+ 1, n + 2}; [( ˆm, 3n+ 1) →(k, 0)]0 1for every k∈ϕ(m)\ {n+ 1, n + 2}. In case that the label of the “trap” n+ 2 is reached then we can immediately enter an infinite loop due to the fact that the additional symbol Fthen still will be present in its indexed variants (F, l),0≤l≤3n+ 1 : [( ¯m, 3n+ 1) →λ]0 1for every mwith n+ 2 ∈σ(m) ; [( ˆm, 3n+ 1) →λ]0 1for every mwith n+ 2 ∈ϕ(m). •The simulation of a derivation in G0by Π may successfully end if we can apply [( ¯m, 3n+ 1) →λ]0 1for n+ 1 ∈σ(m) or [( ˆm, 3n+ 1) →λ]0 1for n+ 1 ∈ϕ(m). Due to our assumptions for G0,after applying such a rule in Π no non-terminal symbol can appear any more (observe that in that case the additional symbol Fhas disappeared, too); hence, in case of termination we finish with an empty membrane. The construction given above completely describes the set of rules RΠof the P system with active membranes Π. For sake of completeness, we finally list all objects from Oobtained according to the construction given above: •E; •afor all a∈T; •(B, l) for all B∈N, 0≤l≤3n+ 1; •(m, l) for all 1 ≤m≤n, 0≤l < 3m; •( ¯m, l),( ˆm, l) for all 3m≤l≤3n+ 1,1≤m≤n; •m0, m00, m000 for all 1 ≤m≤n. From the explanations given above, it is obvious that the P system with active membranes Π defined above exactly generates the same set of objects as the given graph-controlled grammar in the special normal form exhibited in this section, which observation completes the proof. 2 We could also consider P systems with extensions, i.e., in the constructions above we could read every λthere representing the empty word as a special non-terminal symbol not being taken 26 into account when considering the resulting Parikh sets; in such a case, using rules of the form (c) only instead of rules of the form (cλ) would already yield computational completeness. Yet we do not follow this direction in the following, as the related results are obvious and directly follow from the proofs given in this section. Instead, we prove that even with the original types of rules (a) and (c) we only need one additional membrane being only used for filtering out the non-terminal symbols having passed the inner membrane: Theorem 3.2 PsOP2(active2,{a, c}) = PsRE. Proof. Again we only prove that any recursively enumerable set of numbers can be generated by a P system with active membranes now using two membranes, two polarizations, and rules of the types (a) and (c). We again start with a graph-controlled grammar G0=¡N0, T, Lab0, S0, R0,{0},{n+ 1}¢ in the normal form as constructed above which generates the given recursively enumerable set Lof Parikh vectors. We now construct a P system with active membranes of degree two Π = (O, {0,1},[1[2]2]1,(S, 0) (F, 0) (1,0) , λ, 0,0, RΠ) using only two polarizations 0 and 1 and rules of the form (a) and (c) which generates L. The simulation of derivations in the graph-controlled grammar G0by derivations in the P system Π again uses the same colouring technique as described in the previous proof; the simulation of a derivation step is carried out in membrane 2 by opening a “window” of length three for the application of the current rule (i:p(i), σ (i), ϕ (i)) to be applied. The non-terminal symbols sent out through membrane 2 remain unchanged in the region enclosed by the skin membrane. On the other hand, the terminal symbols having passed membrane 2 in the succeeding step leave the system by immediately passing through the skin membrane. In the following, the labels k∈Lab occur in the variants (k, l) and the non-terminal symbols B∈N0occur in the variants (B, l),0≤l≤3n; the label mruns from 1 to n: •As long as the second membrane has polarization 0,the index lof the non-terminal symbols B∈N0in (B, l) may be incremented: [(B, l)→(B, l + 1)]0 2, B ∈N0,0≤l≤3n. •For each m, the index lof m∈Lab in (m, l) is incremented until the index 3m−3 is reached: [(m, l)→(m, l + 1)]0 1,0≤l < 3m−3. •Then we check whether p(m) can be applied to the current contents of membrane 2; by polarizing membrane 2 we first prohibit the incrementation of the index lin the variables of the form (B, l) : [(m, 3m−3) →(m, 3m−2) E]0 2 In the next step, all objects (B, 3m−2) , B ∈N0,in membrane 2 evolve to (B, 3m−1) , whereas (m, 3m−2) evolves to (m, 3m−1) by applying the following rule: [(m, 3m−2) →(m, 3m−1)]0 2 At the same time, Epasses membrane 2 thereby changing its polarization from 0 to 1 : [E]0 2→[ ]1 2E 27 •With the polarization of membrane 2 being 1,the symbols now remain unchanged, only one suitable object – if possible – has to pass the membrane resetting the polarization to 0: [(A(m),3m−1)]1 2→[ ]0 2(A(m),3m−1) At the same time, the object (m, 3m−1) evolves according to the following rule: [(m, 3m−1) →m0]1 2 •In the next step m0evolves according to the polarization of the membrane (the polarization has stored the one-bit information whether A(m) was present or not): If the polarization is still 1,then m0evolves in two further steps to m000, where the symbol Egenerated in the first step then resets the polarization to 0 in the second step by passing the membrane: [m0→m00E]1 2, [m00 →m000]1 2, [E]1 2→[ ]0 2E •As the polarization is 0 again, the symbols (B, 3m−1) , B ∈N0,may evolve to (B, 3m), whereas m0and m000,respectively, evolve to different symbols with index 3m: [m0→( ¯m, 3m)]0 2 [m000 →( ˆm, 3m)]0 2 •The symbols ( ¯m, 3m) and ( ˆm, 3m) until the end of a simulation cycle evolve in the same way as the basic objects (m, l) by incrementing the second parameter: [( ¯m, l)→( ¯m, l + 1)]0 2,3m≤l < 3n; [( ˆm, l)→( ˆm, l + 1)]0 2,3m≤l < 3n. •At the end of a complete cycle, we finally extract the information stored in the symbols ¯mand ˆm, respectively, and start a new cycle: [(B, 3n)→(B, 3n+ 1)]0 2and [(B, 3n+ 1) →(B, 0)]0 2for all B∈N0; [( ˆm, 3n)→( ˆm, 3n+ 1)]0 2or [( ¯m, 3n)→( ¯m, 3n+ 1) h(w(m))]0 2,respectively, where h:N0∪T→(N0,3n+ 1) ∪Tis the morphism with h(B) = (B, 3n+ 1) for all B∈N0and h(a) = afor all a∈T; observe that due to our assumptions about G0, h (w(m)) cannot contain more than one terminal symbol a, which may pass membrane 2 by using the rule [a]0 2→[ ]0 2a and, in the immediately following step, then leaves the skin membrane by using the following rule: [a]0 1→[ ]0 1a 28 t8e3zc2c2 0 2 oooo 1 2yes ooo 1 2yes ooo e3 0 2 0 1 ⇒ t9e3zc2c2 0 2 oooo 1 2 ooo 1 2yes ooo e3 0 2 1 1 yes. Due to the explanations given above one can easily verify that in any case the given algorithm will correctly decide a given satisfiability problem in nvariables and mclauses in n+ 2m+ 4 steps, i.e., in linear time. 2 In Theorem 4.1 we have shown that the NP-complete problem SAT can be decided by a P system with active membranes in linear time with only two polarizations and global rules of types (a),(c),and (e).There remains the open question whether the general form of these rules can be further restricted, e.g., is it possible to replace the rules of type (c) by rules of type (c0),where the application of such a rule does not depend on the polarization of the involved membrane and as well the application of such a rule never changes the polarization of the membrane? References [1] A. Alhazov, C. Mart´ın-Vide, L. Pan, Linear Time Solutions of NP-Complete Graph Problems by P Systems with Restricted Elementary Active Membranes, submitted 2003. [2] A. Alhazov, C. Mart´ın-Vide, L. Pan, Solving a PSPACE-complete Problem by P Systems with Restricted Active Membranes, Fundamenta Informaticae,58, 2 (2003), 67–77. [3] A. Alhazov, L. Pan, Polarizationless P Systems with Active Membranes, Grammars,7, 1 (2004). [4] A. Alhazov, L. Pan, Gh. P˘aun, Trading Polarizations for Labels in P Systems with Active Membranes, submitted 2003. [5] J. Dassow, Gh. P˘aun, Regulated Rewriting in Formal Language Theory. Springer-Verlag, Berlin, 1989. [6] R. Freund, C. Mart´ın-Vide, Gh. P˘aun, From Regulated Rewriting to Computing with Membranes: Collapsing Hierarchies, Theoretical Computer Science,312 (2004), 143–188. [7] R. Freund, Gh. P˘aun, Deterministic P systems, submitted 2004. [8] M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, Solving Numerical NP- Complete Problems Using P Systems with Active membranes: the Partition Problem and Beyond, EMCC Workshop, Vienna (2003). [9] S.N. Krishna, R. Rama, A Variant of P Systems with Active Membranes: Solving NP- Complete Problems, Romanian J. of Information Science and Technology,2, 4 (1999), 357–367. [10] M. Madhu, K. Krithivasan, Improved Results about the Universality of P Systems, Bulletin of the EATCS,76 (February 2002), 162–168. 35 [11] A. ObtuÃlowicz, Deterministic P Systems for Solving SAT Problem, Romanian J. of Information Science and Technology,4, 1-2 (2001), 195–202. [12] A. ObtuÃlowicz, On P Systems with Active Membranes Solving Integer Factorizing Problem in a Polynomial Time, in Multiset Processing. Mathematical, Computer Science, and Molecular Computing Points of View (C.S. Calude, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.), Lecture Notes in Computer Science 2235, Springer-Verlag, 2001, 267–286. [13] A. P˘aun, On P Systems with Global Rules, Proc. 7th Intern. Meeting on DNA Based Computers (N. Jonoska, N.C. Seeman, eds.), Tampa (2001), 43–52. [14] Gh. P˘aun, Computing with Membranes - A Variant: P Systems with Polarized Membranes, Intern. J. of Foundations of Computer Science,11, 1 (2000), 167–182, and CDMTCS TR 098, Univ. of Auckland (1999). [15] Gh. P˘aun, Computing with Membranes: An Introduction, Springer-Verlag, Berlin, 2002. [16] M.J. P´erez-Jim´enez, A. Romero Jim´enez, F. Sancho Caparrini, Teor´ıa de la complejidad en modelos de computaci´on celular con membranas. Kronos Editorial, Sevilla, 2002. [17] M.J. P´erez Jim´enez, A. Romero Jim´enez, F. Sancho Caparrini, Solving VALIDITY Problem by Active Membranes with Input, Brainstorming Week on Membrane Computing, Tarragona, 2003, Rovira i Virgili Univ., Tech. Rep. 26/03 (M. Cavaliere, C. Mart´ın-Vide, Gh. P˘aun, eds.), 279–290. [18] A. Salomaa, G. Rozenberg (eds.), Handbook of Formal Languages, Springer-Verlag, Berlin, 1997. [19] P. Sos´ık, Solving a PSPACE-Complete Problem by P Systems with Active Membranes, Brainstorming Week on Membrane Computing, Tarragona, 2003, Rovira i Virgili Univ., Tech. Rep. 26/03 (M. Cavaliere, C. Mart´ın-Vide, Gh. P˘aun, eds.), 305–312. [20] Cl. Zandron, Cl. Ferretti, G. Mauri, Solving NP-Complete Problems Using P Systems with Active Membranes, in Unconventional Models of Computation (I. Antoniou, C.S. Calude, M.J. Dinneen, eds.), Springer-Verlag, London, 2000, 289–301. 36