P Systems with Active Membranes and Separation Rules

P Systems with Active Membranes and Separation Rules Linqiang PAN1,2, Tseren-Onolt ISHDORJ2 1Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, People’s Republic of China E-mail: [email protected] 2Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T`arraco 1, 43005 Tarragona, Spain E-mail: {lp@fll, tserenonolt.ishdorj@estudiants}.urv.es Abstract. The P systems are a class of distributed parallel computing devices of a biochemical type. In this paper, a new definition of separation rules in P systems with active membranes is given. Under the new definition, the efficiency and universality of P systems with active membranes and separation rules instead of division are investigated. 1 Introduction The P systems are a class of distributed parallel computing devices of a biochemical type, introduced in [7], which can be seen as a general computing architecture where various types of objects can be processed by various operations. The area starts from the observation that certain processes which take place in the complex structure of living organisms can be considered as computations. For a motivation and detailed description of various P system models we refer to [7], [9]. Informally speaking, in P systems with active membranes one uses six types of rules: (a) multiset rewriting rules, (b) rules for introducing objects into membranes, (c) rules for sending objects out of membranes, (d) rules for dissolving membranes, (e) rules for dividing elementary membranes, and (f) rules for dividing non-elementary membranes. Membrane division – inspired from cell division well-known in biology – is the most investigated way for obtaining an exponential working space in a linear time, and solving on this basis hard problems, typically NP-complete problems, in polynomial (often, linear) time. Details can be found in [8, 9, 10]. Recently, also PSPACE-complete problems were attacked in this way (see [13, 2]). Separation is also a well known phenomenon of cell biology. Many macromolecules are too large to be transported through membranes by means of vesicle formation. This process can transport packages of chemicals out of the cell. 325 By division, the two new membranes have exactly the same objects except for at most a pair of different objects; it is also possible that the two new membranes have different charges. However, in the biological phenomenon of separation, the two new membranes evolved from a membrane can have much difference, such as the number of objects. In [1], separation rules are introduced to P systems with active membranes, where for each separation rule, a different subset Uof objects is defined to activate the membrane to separate, and by Uobjects are put into the two new membranes. In this paper, we give a new definition of separation rules. In the new definition, for each separation rule one object is used to activate separation; for all separation rules a uniform subset O1of objects is used to denote which membrane objects should go. From this point of view, the new definition is an improvement of the definition in [1]. Under the new definition, the efficiency and universality of P systems with active membranes and separation rules instead of division are investigated. 2 P Systems with Active Membranes We assume the reader to be familiar with basic elements of complexity theory and formal language theory, for instance, from [6, 12, 11], as well as with the basic knowledge of membrane computing, for instance, from [9] (details and recent results from membrane computing can be found at the web address http://psystems.disco.unimib.it). We only mention that RE denote the family of recursively enumerable languages, and that for a family of languages FL, by P sF L we denote the family of Parikh sets of languages in FL; as usual, the Parikh mapping associated with an alphabet Vis denoted by ΨV. A P system with active membranes (and electrical charges) is a construct Π = (O, H, µ, w1, . . . , wm, R), where: 1. m≥1 (the initial degree of the system); 2. Ois the alphabet of objects, where O=O1∪O2,O1, O26=∅,O1∩O2=∅; 3. His a finite set of labels for membranes; 4. µis a membrane structure, consisting of mmembranes, labeled (not necessarily in a one-to-one manner) with elements of H; 5. w1, . . . , wmare strings over O, describing the multisets of objects placed in the m regions of µ; 6. Ris a finite set of developmental rules, of the following forms: (a) [ a→v]e h, for h∈H, e ∈ {+,−,0}, a ∈O, v ∈O∗ (object evolution rules, associated with membranes and depending on the label and the charge of the membranes, but not directly involving the membranes, in the sense that the membranes are neither taking part in the application of these rules nor are they modified by them); 326 (b)a[ ]e1 h→[b]e2 h, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (communication rules; an object is introduced in the membrane, possibly modified during this process; also the polarization of the membrane can be modified, but not its label); (c) [ a]e1 h→[ ]e2 hb, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (communication rules; an object is sent out of the membrane, possibly modified during this process; also the polarization of the membrane can be modified, but not its label); (d) [ a]e h→b, for h∈H, e ∈ {+,−,0}, a, b ∈O (dissolving rules; in reaction with an object, a membrane can be dissolved, while the object specified in the rule can be modified); (e) [ a]e1 h→[b]e2 h[c]e3 h, for h∈H, e1, e2, e3∈ {+,−,0}, a, b, c ∈O (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; the object specified in the rule is replaced in the two new membranes by possibly new objects); (f) [ [ ]α1 h1. . . [ ]α1 hk[ ]α2 hk+1 . . . [ ]α2 hn]α0 h0 →[ [ ]α3 h1. . . [ ]α3 hk]α5 h0[ [ ]α4 hk+1 ...[ ]α4 hn]α6 h0, for k≥1, n > k, hi∈H, 0≤i≤n, and α0, . . . , α6∈ {+,−,0}with {α1, α2}={+,−}; if the membrane with the label h0contains other membranes than those with the labels h1, . . . , hnspecified above, then they must have neutral charges in order to make this rule applicable; these membranes are duplicated and then are part of the contents of both new copies of the membrane h0 (division of non-elementary membranes; this is possible only if a membrane contains two immediately lower membranes of opposite polarization, + and −; the membranes of opposite polarizations are separated in the two new membranes, but their polarization can change; always, all membranes of opposite polarizations are separated by applying this rule). (Note that, in order to simplify the writing, in contrast to the style customary in the literature, we have omitted the label of the left parenthesis from a pair of parentheses which identifies a membrane.) The rules of type (a) are applied in the parallel way (all objects which can evolve by such a rule should do it), while the rules of types (b),(c),(d),(e),(f) are used sequentially, in the sense that one membrane can be used by at most one rule of these types at a time. In total, the rules are used in the non-deterministic maximally parallel manner: all objects and all membranes which can evolve, should evolve. Only halting computations give a result, non-halting computations give no output. The separation rules introduced in [1] are of the following form (without polarizations): (h0) [ O]h→[U]h[O−U]h, for h∈H, U ⊂O. If polarization is considered, they will be of the form: (h) [ O]e1 h→[U]e2 h[O−U]e3 h, for h∈H, U ⊂O. 327 Here, we introduce a new definition of separation rules. (g) [ a]e1 h→[O1]e2 h[O2]e3 h, for h∈H,e1, e2, e3∈ {+,−,0},a∈O (separation rules for elementary membranes; in reaction with an object, the membrane is separated into two membranes with the same label, possibly different polarization; at the same time, the object acan evolve; the objects from O1are placed in the first membrane, those from O2are placed in the second membrane). As the rules of types (b),(c),(d),(e), and (f), the rules of type (g) are used sequentially, in the sense that one membrane can be used by at most one rule of these types at a time. If at the same time a membrane his separated, and there are objects in this membrane which evolve by means of rules of type (a), then in the two new membranes we introduce the result of evolution; that is, we suppose that first the evolution rules of type (a) are used, changing the objects, then separation is produced. Of course, this process takes one step. Note the difference between division rule and separation rule. In division rule, except for the object specified in the rule is replaced by two possibly different new objects, the two new membranes have the same copy of objects. But in separation rule, the new objects are placed into the two new membranes according to O1and O2, these two new membranes can have much difference, such as the number of objects. For the difference between the definitions of (g) and (h), see the introduction. To understand what it means solving a problem in a uniform and confluent way, here we briefly recall some related notions. Given a decision problem X, we say that it can be solved in polynomial (linear) time by recognizing P systems in a uniform way, if, informally speaking, we can construct in polynomial time a family of recognizing P systems Πn,n∈N, associated with the sizes nof instances X(n) of the problem, such that the system will always stop in a polynomial (linear, respectively) number of steps, sending out the object yes if the instance X(n) has a positive answer and the object no if the instance X(n) has a negative answer. If the computation of a P system is nondeterministic, but all branches of a computation eventually reach a unique configuration, then we say that the system is confluent. In the next section, we will show that P systems with separation rules instead of division rules can solve the SAT problem in linear time in a uniform and deterministic way. 3 Solving SAT by P Systems with Separation Rules Theorem 3.1 P systems with rules of types (a),(b),(c), and (g)can solve SAT in linear time in a uniform and deterministic way. Proof. Let us consider a propositional formula in the conjunctive normal form: β=C1∧ · · · ∧ Cm, Ci=yi,1∨ · · · ∨ yi,li,1≤i≤m, where yi,k ∈ {xj,¬xj|1≤j≤n},1≤i≤m, 1≤k≤li. The instance β(to which the size (m, n) is associated) is encoded as a multiset over V(hn, mi) = {xi,j,¯xi,j |1≤i≤m, 1≤j≤n}. 328 The object xi,j represents the variable xjappearing in the clause Ciwithout negation, and object ¯xi,j represents the variable xjappearing in the clause Ciwith negation. Thus, the input multiset is w={xi,j |xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n} ∪ {¯xi,j | ¬xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}. For given (n, m)∈N2, we construct a recognizing P system (Π(hn, mi), V (hn, mi),2) with: Π(hn, mi)=(O(hn, mi), H, µ, w1, w2, R), O(hn, mi) = O1∪O2, O1={xi,j,¯xi,j,|0≤i≤m, 1≤j≤n} ∪ {ci|1≤i≤m+ 2} ∪ {di|1≤i≤2n+ 2m+ 2}∪{ri,j |0≤i≤m, 1≤j≤n} ∪ {e, t, λ, yes,no}, O2={x0 i,j,¯x0 i,j,|0≤i≤m, 1≤j≤n} ∪ {d0 i|1≤i≤n} ∪ {ri,j |0≤i≤m, 1≤j≤n}∪{e0}, µ= [ [ ]2]1, w1=λ, w2=d1, H={1,2}, and the following rules (we also give explanations about the use of these rules): 1. [ di]0 2→[O1]+ 2[O2]− 2, 1 ≤i≤n. In membrane with label 2, when it is “electrically neutral”, object dicauses the membrane to separate and to choose for a variable xi, 1 ≤i≤n, both values true and false, in form of charges + and −of the two created membranes with the label 2. These rules allow us to have 2ninternal membranes, in nsteps. 2. [ xi,j →xi,jx0 i,j]0 2, 1 ≤i≤m, 1 ≤j≤n. [ ¯xi,j →¯xi,j ¯x0 i,j]0 2, 1 ≤i≤m, 1 ≤j≤n. [di→di+1ed0 i+1e0]0 2, 1 ≤i≤n−1. At the same time with using the rule of type (1), the objects evolve by rules of type (2). 3. [ xi,1→ri,1]+ 2, 1 ≤i≤m. [ ¯xi,1→λ]+ 2, 1 ≤i≤m. [x0 i,1→λ]− 2, 1 ≤i≤m. [ ¯x0 i,1→r0 i,1]− 2, 1 ≤i≤m. The rules of type (3) try to implement a process allowing 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,1or r0 i,1will appear in the membrane. In other case, the object encoding the variable will disappear. 4. [ xi,j →xi,j−1]+ 2, 1 ≤i≤m, 2 ≤j≤n. [ ¯xi,j →¯xi,j−1]+ 2, 1 ≤i≤m, 2 ≤j≤n. [x0 i,j →xi,j−1]− 2, 1 ≤i≤m, 2 ≤j≤n. 329 [ ¯x0 i,j →¯xi,j−1]− 2, 1 ≤i≤m, 2 ≤j≤n. The check process described in the rules of type (3) is always made with respect to the first variable appearing in the internal membrane. Hence, the rules of type (4) 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. 5. [ e]+ 1→[ ]0 1e. [e0]− 1→[ ]0 1e. [d0 i→di]− 2, 1 ≤i≤n. The auxiliary objects eand e0exit the membrane changing the polarizations to neutral and the object d0 iin the membrane with negative charge evolves to the object di(for the use of the rules of type (1) and the third rules of type (2)), so that the above described generating process of the assignments and the encoding of the satisfied clauses can cycle. 6. [ ri,k →ri,k+1r0 i,k+1]0 2, for 1 ≤i≤m, 1 ≤k≤n−1. [r0 i,k →ri,k+1r0 i,k+1]0 2, for 1 ≤i≤m, 1 ≤k≤n−1. These rules are designed to denote the fact: if clause Ciis satisfied by the assignment encoded by a membrane, then the new membranes obtained from it by separation also satisfy the clause Ci. The second subscript of ri,k or r0 i,k is used for synchronization, which is necessary, because of the use of objects ri,n and r0 i,n in the rules of types (11), (12), and (13). 7. [ di→di+1]0 2, for n≤i≤2n−2. [d2n−2→d2n−1c1]0 2. Through the counter objects di, the rules of type (7) control the process of synchronization of the objects ri,k and r0 i,k in the internal membranes. 8. [ d2n−1]0 2→[ ]+ 2d2n−1. The application of the rules of type (8) will show that the system is ready to check which clauses are true by the assignment encoded by an internal membrane. 9. [ di→di+1]0 1, 2n−1≤i≤2n+ 2m+ 1. The rules of type (9) supply counter objects diin the skin, in such a way that, if objects d2n+2m−1appear, then they show the end of the checking of the clauses. The objects di, with 2n+ 2m≤i≤2n+ 2m+ 2, will control the final stage of the computation. 10. [ r1,n]+ 2→[ ]− 2r1,n. [r0 1,n]+ 2→[ ]− 2r1,n. For all 2ninternal membranes, we check whether r1,n or r0 1,n is present in each membrane. If this is the case, then r1,n or r0 1,n is sent out of the membrane where it is present (one copy of r1,n or r0 1,n exits the membrane where it is present, the other copies will evolve to r0,n or r0 0,n by the rules of type (10), which will never evolve again), changing in this way the polarization of that membrane, to negative. The membranes which do not contain the object r1,n or r0 1,n remain positive and they will no longer evolve, as no further rule can be applied to them. 11. [ ri,n →ri−1,n]− 2, for 1 ≤i≤n. [r0 i,n →r0 i−1,n]− 2, for 1 ≤i≤n. 330 The rules of type (10) always work with respect to the objects r1,n or r0 1,n, The relabel in the rules of type (11) takes charge of making a cyclic path through all ri,n and r0 i,n, and evolves the objects r1,n or r0 1,n to r0,n or r0 0,n (which will never evolve again). 12. r1,n[ ]− 2→[r0,n]+ 2. The objects r1,n from the skin membrane return to internal membranes with negative charge, changing to r0,n, and returning the polarization of the membrane to positive. This makes possible the use of rules of type (10). Note that in the skin membrane the number of copies of r1,n is equal to the number of membranes with negative charge; thus, because of parallelism, each membrane which previously contained objects r1,n or r0 1,n will now contain an object r0,n. 13. [ ci→ci+1]− 2, 1 ≤i≤m. The presence of object ci(with 2 ≤i≤m+ 1) in the internal membrane shows that the assignment makes the first i−1 clauses true. 14. [ cm+1]+ 2→[ ]+ 2cm+1. The presence of the object cm+1 shows that all clauses are satisfied by the assignment encoded by an internal membrane. The rule of type (14) sends to the skin the objects cm+1 appearing in the internal membranes. 15. [ cm+1 →cm+2t]0 1. The objects cm+1 in the skin evolve to objects cm+2t. The objects tin the skin are produced simultaneously with the appearance of the objects d2n+2m+1 in the skin, and they will be used to output the computing result. 16. [ t]0 1→[ ]+ 1t. The rule of type (16) sends out of the system an object tchanging the polarization of the skin to positive, then objects tremaining in the skin are not able to evolve. Then by rule of type (17), the object cm+2 can exit the skin producing an object yes, telling us that the formula is satisfiable, and the computation halts. 17. [ cm+2]+ 1→[ ]− 1yes. The application of the rule of type (17) changes the polarization in the skin membrane to negative in order that the objects cm+2 remaining in it are not able to continue evolving. 18. [ d2n+2m+2]0 1→[ ]+ 1no. By the rule (18) the object d2n+2m+2 only evolves when the skin has neutral charge (this is the case when the formula is not satisfiable). Then the system will evolve sending out to the environment an object no and changing the polarization of the skin to positive, in order that objects d2n+2m+2 remaining in the skin, do not evolve. From the previous explanation of the use of rules, one can easily see how this P system works. It is clear that the object yes is sent to the environment if and only if the formula βis satisfiable. This is achieved in 3n+ 2m+ 4 steps: in 2nsteps we create 2ninternal membranes (as well as the 2ndifferent truth-assignments), then nsteps for synchronization; it takes 2msteps to check whether all clauses are satisfied by an assignment; further 4 steps are necessary to output the computing result yes. If formula 331 βis not satisfiable, then at step 3n+ 2m+ 4 the system sends the object no to the environment. Therefore, the family of membrane systems we have constructed is sound, confluent, and linearly efficient. To prove that the family is uniform, we have to show that for a given size, the construction of P systems described in the proof can be done in polynomial time by a Turing machine. We omit the detailed construction due to the fact that it is straightforward but cumbersome as explained in the proof of Theorem 7.2.3 in [9] (although P systems in [9] are semi-uniform). So SAT problem was decided in linear time (3n+2m+2) by recognizing active P systems with separation rule in a uniform way, and this concludes the proof. 2 4 Removing Polarizations Following the idea in [3, 4], let us consider now rules of types (a)−(e) and (g) without polarizations. They are of the following forms (because “no polarization” means “neutral polarization”, we add the subscript 0 to the previous letters identifying the six types of rules; as above, O=O1∪O2is the alphabet of objects and His the set of labels of membranes): (a0) [ a→v]h, where a∈O, v ∈O∗, and h∈H, (b0)a[ ]h→[b]h, where a, b ∈Oand h∈H, (c0) [ a]h→[ ]hb, where a, b ∈Oand h∈H, (d0) [ a]h→b, where a, b ∈Oand h∈H, (e0) [ a]h→[b]h[c]h, where a, b, c ∈Oand h∈H, (g0) [ a]h→[O1]h[O2]h, for h∈H,a∈O. Rules of types (b),(c),(e),(g) in Section 2 were introduced without the capability of changing the label of membranes they involve (this makes no sense for dissolving rules), but in [9] one already considers rules of type (e) which can change both the label and the polarization of membranes. Such rules are of the form [a]e1 h1→[b]e2 h2[c]e3 h3,with a, b, c ∈O, e1, e2, e3∈ {+,−,0},and h1, h2, h3∈H, and they have been called of type (e0). We extend this idea and this notation to rules of types (b0), (c0), (e0), (g0): their primed versions indicate the fact that the labels can be changed. Specifically, these rules are of the following forms: (b0 0)a[ ]h1→[b]h2, where a, b ∈Oand h1, h2∈H, (c0 0) [ a]h1→[ ]h2b, where a, b ∈Oand h1, h2∈H, (e0 0) [ a]h1→[b]h2[c]h3, where a, b, c ∈Oand h1, h2, h3∈H, (g0 0) [ a]h1→[O1]h2[O2]h3, for h1, h2, h3∈H,a∈O. In the following, we consider the efficiency and universality of active P systems without polarization with separation rules instead of division. 332 4.1 Efficiency Theorem 4.1 P systems with rules of types (a0),(b0),(c0),(g0 0)can solve SAT in linear time in a uniform and confluent way. Proof. Let us consider a propositional formula in the conjunctive normal form: β=C1∧ · · · ∧ Cm, Ci=yi,1∨ · · · ∨ yi,li,1≤i≤m, where yi,k ∈ {xj,¬xj|1≤j≤n},1≤i≤m, 1≤k≤li. The instance β(to which the size (m, n) is associated) is encoded as a multiset over V(hn, mi) = {xi,j,¯xi,j |1≤i≤m, 1≤j≤n}. The object xi,j represents the variable xjappearing in the clause Ciwithout negation, and object ¯xi,j represents the variable xjappearing in the clause Ciwith negation. Thus, the input multiset is w={xi,j |xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n} ∪ {¯xi,j | ¬xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}. For given (n, m)∈N2, we construct a recognizing P system (Π(hn, mi), V (hn, mi),2) with: Π(hn, mi)=(O(hn, mi), H, µ, w1, w2, w7, R), O(hn, mi) = O1∪O2, O1={xi,j,¯xi,j |1≤i≤m, 0≤j≤n}∪{di|0≤i≤2n+ 2m+ 6} ∪ {ci|1≤i≤m} ∪ {λ, e, f0, f1,yes,no}, O2={x0 i,j,¯x0 i,j |1≤i≤m, 0≤j≤n}∪{d0 i|0≤i≤n−1} ∪ {c0 i|1≤i≤m}, µ= [ [ ]2[ ]7]1, w1=λ, w2=w7=d0, H={0,1,2,3,4,5,6,7}, and the following rules (we also give explanations about the use of these rules): Generation phase G1 [ di]2→[O1]3[O2]4, 0 ≤i < n. [di→did0 i]2, 0 ≤i < n. G2 [ di]3→[O1]2[O2]0, 0 ≤i < n. [di→di+1d0 0]3, 0 ≤i < n. G3 [ d0 i]4→[O1]2[O2]0, 0 ≤i < n. [d0 i→di+1d0 0]4, 0 ≤i < n. G4 [ dn]2→[O1]5[O2]0. [dn→d0d0 0]2. 333 8. [ A→#]f, for all A∈N2. 9. [ # →#]h,for all h∈H. 10. [ a]f→[ ]fa. 11. [ a]1→[ ]1a, for all a∈T. The equality ΨT(L(G)) = Ps(Π) easily follows from the above explanations. 2 Remark 4.1 In the above proof, the rules of type (c0)are only used for sending the result of a computation out of the system. Therefore, rules of types (a0)and (g0 0)are sufficient to reach universality for membrane systems with internal output. 5 Final Remark In this paper, separation is introduced into active P systems, and the efficiency and universality of active P systems with separation rules instead of division are investigated. The universality result is obtained by a direct proof. It still remains open using P systems with separation rules to simulate P systems with division rules. Acknowledgements. The authors acknowledge IST-2001-32008 project “MolCoNet”. The first author (he is also the corresponding author) is also supported by grant DGUSB2001-0092 from Spanish Ministry of Education, Culture, and Sport, National Natural Science Foundation of China (Grant No. 60373089), and Huazhong University of Science and Technology Foundation. The second author acknowledges The State Training Fund of the Ministry of Science, Technology, Education and Culture of Mongolia. References [1] A. Alhazov, T.-O. Ishdorj, Membrane Operations in P Systems with Active Membranes, Manuscript circulated during the Second Brainstorming Week on Membrane Computing, Sevilla, Spain, Feb. 2-7, 2004. [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), 66–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] Ch. P. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994. [7] Gh. P˘aun, Computing with Membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143, 340 [8] Gh. P˘aun, P Systems with Active Membranes: Attacking NP-Complete Problems, Journal of Automata, Languages and Combinatorics, 6, 1 (2001), 75–90. [9] Gh. P˘aun, Computing with Membranes: An Introduction, Springer-Verlag, Berlin, 2002. [10] M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini, Teor´ıa de la Complejidad en Modelos de Computati´on Celular con Membranas, Editorial Kronos, Sevilla, 2002. [11] G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages (3 volumes), Springer-Verlag, Berlin, 1997. [12] A. Salomaa, Formal Languages, Academic Press, New York, 1973. [13] P. Sos´ık, Solving a PSPACE-Complete Problem by P Systems with Active Membranes, Proceedings of the Brainstorming Week on Membrane Computing (M. Cavaliere, C. Mart´ın-Vide, and Gh. P˘aun, eds.), Report GRLMC 26/03, 2003, 305–312. 341