9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Trading Polarizations for Labels in P Systems with Active Membranes

Trading Polarizations for Labels in P Systems with Active Membranes

? Artiom ALHAZOV1,2 , Linqiang PAN1,3 , Gheorghe PAUN1,4

Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T`rraco 1, 43005 Tarragona, Spain a {artiome.alhazov@estudiants, lp@fll, gp@astor}.urv.es 2 Institute of Mathematics and Computer Science Academy of Science of Moldova Str. Academiei 5, Chi?in?u, MD 2028, Moldova s a artiom@math.md 3 Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, People’s Republic of China lqpan@mail.hust.edu.cn 4 Institute of Mathematics of the Romanian Academy PO Box 1-764, 70700 Bucure?ti, Romania s george.paun@imar.ro

1

Abstract. This paper addresses the problem of removing the polarizations of membranes from P systems with active membranes – and this is achieved (sometimes, in restricted circumstances which we do not specify here) by allowing the change of membrane labels by means of communication rules (speci?cally, by rules sending objects out of membranes) or by membrane dividing rules. As consequences of these results, we obtain the universality of P systems with active membranes which are allowed to change the labels of membranes, but not using polarizations. Universality results are easily obtained also by direct proofs (this is achieved also for communication rules which bring objects into membranes). By direct constructions, we also prove that SAT can be solved in linear time by systems without polarizations and with label changing possibilities. Somewhat surprisingly, if non-elementary membranes can be divided, then SAT can be solved in linear time without using polarizations and label changing. Several open problems are also formulated.

1

Introduction

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, 11]. Recently, also PSPACE-complete problems were attacked in this way (see [14, 1]).

Corresponding author.

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. For most of this paper we discuss only rules of the ?rst ?ve types; rules for dividing non-elementary membranes are used only in Section 5, in a particular form which we will introduce directly there. All these rules are associated with membranes, while membranes have both a label, from a ?nite set of labels, and an “electrical polarization”, which can be +, ?, or 0 (for “neutral”). Moreover, rules of types (b), (c), and (e) (as well as (f ), but we ignore for the time being this case) can change the polarization of the membranes they involve (but always they preserve the label of the membranes; in particular, the dividing rules of the “standard” form produce two membranes with the same label as the divided membrane). However, the electrical charges used in this context are not quite realistic from a biological point of view. The cell membrane is polarized, but in a di?erent manner: it is in general positively charged in the external layer and negatively charged in the inner layer of phospholypidic molecules. On the other hand, it is possible to have an overall polarization, positive or negative, of inner vesicles, due to ion exchanges with the inner or upper compartments, but the changes of these polarizations are done by more complex processes than by applying single rules as in P systems with active membranes. Anyway, it is a natural question to consider systems without membrane polarizations – this is to say, systems whose membranes always have the same polarization, for instance, they are neutral. What is the power and what is the e?ciency of such systems? In particular, are they universal? Can they solve SAT in linear time? The general questions above remain open and we give here only a partial answer to them. First, we prove that without polarizations we can compute the Parikh sets of matrix languages (generated by grammars without appearance checking), and also the Parikh sets of some non-matrix languages. Then, we address a simpler problem: what else can be added to P systems with active membranes such that by removing the polarizations we still get universality and polynomial solutions to NP-complete problems? A suggestion comes already from [9], although not introduced there with this goal: let us allow the membrane division rules to introduce membranes with new labels, not necessarily with the same label as the divided membrane. The idea can be extended also to rules of types (b) and (c): change the label of a membrane when introducing or expelling an object in/from a membrane. As we shall see below, this works, at least for rules of types (c) and (e): systems with polarized membranes can be simulated by systems with non-polarized membranes, providing that we can change the labels of membranes when sending objects out of them or when dividing them. For rules of type (e) the result is true for systems with only two levels of membranes which never change the polarization of the skin. Note that this is somewhat similar to the biological 2

observation mentioned above, that the inner vesicles of a cell might be polarized, while, moreover, two levels of membranes is a good approximation of the structure of a cell. Pleasantly enough, for proving the universality of P systems with active membranes (and polarizations), systems of depth two su?ce, and they do not change the polarization of the skin. Thus, in both cases, we get the universality as a corollary of the above mentioned results (and the known proof of universality from [5, 9] – slightly modi?ed). The case of rules of type (b) remains open: can a P system with active membranes and polarizations be simulated by a system without polarizations but allowed to change the label of membranes when introducing objects into them? Even without such a simulation lemma, the universality can be obtained also in this case, by a (surprisingly simple) direct proof. Unfortunately, the proofs of the two simulation results mentioned above have a drawback: they introduce non-determinism in the functioning of the system. This means that they do not imply that SAT can be solved in polynomial time by systems without polarizations – but this is directly proven, for the two “easy” cases, of changing labels by rules of type (c), or (e) (and again it remains open for the case of rules of type (b)). An interesting result is obtained when using rules of type (f ), for dividing non-elementary membranes: SAT is solved in linear time (by a system constructed in semi-uniform manner) without using polarizations and label changing (the universality remains open in this case).

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, 13, 12], 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 REG, CF, CS, RE denote the families of languages from Chomsky hierarchy (regular, context-free, context-sensitive, recursively enumerable languages, respectively), and that for a family F L, by P sF L we denote the family of Parikh sets of languages in F L; as usual, the Parikh mapping associated with an alphabet V is denoted by ΨV . A P system with active membranes (and electrical charges) is a construct Π = (O, H, ?, w1 , . . . , wm , R), where: 1. 2. 3. 4. m ≥ 1 (the initial degree of the system); O is the alphabet of objects; H is a ?nite set of labels for membranes; ? is a membrane structure, consisting of m membranes, labeled (not necessarily in a one-to-one manner) with elements of H; 3

5. w1 , . . . , wm are strings over O, describing the multisets of objects placed in the m regions of ?; 6. R is a ?nite set of developmental rules, of the following forms: e (a) [ a → v] 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 modi?ed by them); e e (b) a[ ] h1 → [ b] h2 , for h ∈ H, e1 , e2 ∈ {+, ?, 0}, a, b ∈ O (communication rules; an object is introduced in the membrane, possibly modi?ed during this process; also the polarization of the membrane can be modi?ed, but not its label); e e (c) [ a ] h1 → [ ] h2 b, for h ∈ H, e1 , e2 ∈ {+, ?, 0}, a, b ∈ O (communication rules; an object is sent out of the membrane, possibly modi?ed during this process; also the polarization of the membrane can be modi?ed, but not its label); e (d) [ a ] 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 speci?ed in the rule can be modi?ed); e e e (e) [ a ] h1 → [ b ] h2 [ c ] h3 , 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 di?erent polarizations; the object speci?ed in the rule is replaced in the two new membranes by possibly new objects). (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 identi?es a membrane. For the time being, we have also omitted the rules for dividing non-elementary membranes, usually identi?ed as being “of type (f )”.) 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) 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 nondeterministic maximally parallel manner: all objects and all membranes which can evolve, should evolve. Only halting computations give a result, and the result is the vector of natural numbers describing the multiplicity of objects expelled into the environment during the computation; the set of vectors computed in this way by the various halting computations in Π is denoted by P s(Π). (Non-halting computations give no output.) By P sOP (a, b, c, d, e) we denote the family of sets P s(Π) computed as sketched above by systems using all types of rules; when rules of a certain type are not used the corresponding letter a, b, c, d, e will be missing. Details can be found in [9] – including the proof of the following result. 4

Theorem 1. P sOP (a, b, c) = P sRE. In [9], this result is given for sets of natural numbers, hence one-dimensional vectors, but the extension to vectors of arbitrary dimensions is obvious and it holds with the same proof.

3

Removing the Polarizations

Let us consider now rules – of types (a) ? (e) – 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 ?ve types of rules; as above, O is the alphabet of objects and H is the set of labels of membranes): (a0 ) (b0 ) (c0 ) (d0 ) (e0 ) [ a → v] h , where a ∈ O, v ∈ O? , and h ∈ H, a[ ] h → [ b] h , where a, b ∈ O and h ∈ H, [ a] h → [ ] h b, where a, b ∈ O and h ∈ H, [ a] h → b, where a, b ∈ O and h ∈ H, [ a] h → [ b] h [ c] h , where a, b, c ∈ O and h ∈ H.

What is the power of P systems using such rules? Speci?cally: what is the size of the family P sOP (a0 , b0 , c0 , d0 , e0 )? Is it equal to P sRE? If not (as we expect), then what about its relation with P sET 0L (the Parikh sets of ET0L languages)? We leave these problems open, and we only prove here that we can cover in this way at least the Parikh sets of languages generated by matrix grammars without appearance checking. Because the notion of a matrix grammar will be also used below, we introduce it here in its general form. A matrix grammar with appearance checking is a construct G = (N, T, S, M, F ), where N, T are disjoint alphabets, S ∈ N , M is a ?nite set of sequences of the form (A1 → x1 , . . . , An → xn ), n ≥ 1, of context-free rules over N ∪ T (with Ai ∈ N, xi ∈ (N ∪ T )? , in all cases), and F is a set of occurrences of rules in M (N is the nonterminal alphabet, T is the terminal alphabet, S is the axiom, while the elements of M are called matrices). For w, z ∈ (N ∪ T )? we write w =? z if there is a matrix (A1 → x1 , . . . , An → xn ) in M and the strings wi ∈ (N ∪ T )? , 1 ≤ i ≤ n + 1, such that w = w1 , z = wn+1 , and, for all 1 ≤ i ≤ n, either wi = wi Ai wi , wi+1 = wi xi wi , for some wi , wi ∈ (N ∪ T )? , or wi = wi+1 , Ai does not appear in wi , and the rule Ai → xi appears in F . (The rules of a matrix are applied in order, possibly skipping the rules in F if they cannot be applied – therefore we say that these rules are applied in the appearance checking mode.) The language generated by G is de?ned by L(G) = {w ∈ T ? | S =?? w}. The family of languages of this form is denoted by M ATac . If the set F is empty, then the grammar is said to be without appearance checking; the corresponding family of languages is denoted by M AT . It is known that CF ? M AT ? M ATac = RE, P sREG = P sCF ? P sM AT ? P sRE, and that CS ? M AT = ?, P sCS ? P sM AT = ? (for instance, the one-letter languages in M AT are known to be regular, [4]). 5

A matrix grammar G = (N, T, S, M, F ) is said to be in the binary normal form if N = N1 ∪ N2 ∪ {S, #}, with these three sets mutually disjoint, and the matrices in M are in one of the following forms: 1. 2. 3. 4. (S → XA), with X ∈ N1 , A ∈ N2 , (X → Y, A → x), with X, Y ∈ N1 , A ∈ N2 , x ∈ (N2 ∪ T )? , |x| ≤ 2, (X → Y, A → #), with X, Y ∈ N1 , A ∈ N2 , (X → λ, A → x), with X ∈ N1 , A ∈ N2 , and x ∈ T ? , |x| ≤ 2.

Moreover, there is only one matrix of type 1 (that is why one uses to write it in the form (S → Xinit Ainit ), in order to ?x the symbols X, A present in it), and F consists exactly of all rules A → # appearing in matrices of type 3; # is a trap-symbol, because once introduced, it is never removed. A matrix of type 4 is used only once, in the last step of a derivation. For each matrix grammar there is an equivalent matrix grammar in the binary normal form (this is true both for grammars with appearance checking and without appearance checking; in the latter case, the set F and the matrices of type 3 are missing). Details can be found in [3]. The following result is non-trivial, because P sM AT ? P sCF = ? (there are non-semilinear sets of vectors in P sM AT , which is not the case with P sCF ), but gives only a partial answer to the question how powerful P systems without polarizations are. Theorem 2. P sM AT ? P sOP (a0 , b0 , c0 , d0 , e0 ), strict inclusion. Proof. Let us consider a matrix grammar (without appearance checking) G = (N, T, S, M ) in the binary normal form, hence with N = N1 ∪N2 ∪{S}, and with matrices of the types 1, 2, 4 speci?ed above. We assume all matrices of types 2 and 4 labeled in a one-to-one manner with m2 , m3 , . . . , mt , for t ? 1 being the number of these matrices (note that the subscripts of labels start from 2). The terminal matrices mi : (X → λ, A → x) are replaced by mi : (X → f, A → x), for f being a new symbol (the label of the matrix remains the same). We construct the P system ? ? Π = (O, {1, 2}, [ [ ] 2 ] 1 , Xinit Ainit , c, R), where ? ? O = N1 ∪ N2 ∪ T ∪ {X | X ∈ N1 } ∪ {A, A , A | A ∈ N2 } ∪ {Xi,j , Xi | X ∈ N1 , 1 ≤ i ≤ t + 1, ?1 ≤ j ≤ t} ∪ {Ai,j , Ai , Ai | A ∈ N2 , 1 ≤ i ≤ t + 1, 0 ≤ j ≤ t} ? ∪ {c, c1 , c2 , c2 , f, f , #} ∪ {di | 0 ≤ i ≤ t + 1}, and the set R contains the following rules (together with the rules we give explanations about their use and the functioning of the system Π; in the rules below, we use the morphisms hj , 1 ≤ j ≤ t + 1, de?ned by hj (A) = Aj for all A ∈ N2 , and hj (a) = a for all a ∈ T ): 6

? 1. [X → X] 1 , for all X ∈ N1 , ? → A] , for all A ∈ N2 , [A 1 [ c] 2 → [ c1 ] 2 [ c2 ] 2 , [ c → #] 2 . While all symbols from the skin region lose the bars, the inner membrane is divided into two membranes with the same label 2 and containing the auxiliary symbols c1 , c2 , respectively. In the membrane containing c1 we will simulate a matrix of G; at the end of the simulation, this membrane will be dissolved, and the second membrane will be used as starting membrane with label 2, for a further division. 2. X[ ] 2 → [ Xi,?1 ] 2 , for some mi : (X → Y, A → x) ∈ M , 2 ≤ i ≤ t, [ X → #] 1 , for all X ∈ N1 , [ c2 ] 2 → [ ] 2 c2 , [ c2 → #] 2 , [ A → A ] 1 , for all A ∈ N2 . In the second step of the computation, all symbols A ∈ N2 get primed, while the unique symbol from N1 should enter the membrane with label 2 having inside the object c1 – otherwise, either X introduces the trap-object # in the skin region, or, if it enters the membrane containing the object c2 , this object cannot exit the membrane and introduces #. 3. [ Xi,?1 → Xi,0 ] 2 , for all X ∈ N1 , 2 ≤ i ≤ t, [ A → A ] 1 , for all A ∈ N2 , B [ ] 2 → [ Bj,0 ] 2 , for some mj : (Z → U, B → y) ∈ M , 2 ≤ j ≤ t, [ c2 → #] 1 , c2 [ ] 2 → [ d0 ] 2 . In the third step, also a symbol B ∈ N2 can enter into membrane 2 which contains c1 ; we will see below that this is obligatory, otherwise the symbol X – with subscripts – already present there will introduce #. At the same time, all symbols from the skin get double primed and c2 enters the second membrane with label 2 transformed into d0 ; we will also see below that if c2 enters the ?rst membrane with label 2, then the computation will never halt. 4. [ [ [ [ Xi,0 → Xi,1 ] 2 , for all X ∈ N1 , 2 ≤ i ≤ t, Bj,0 → Bj,1 ] 2 , for all A ∈ N2 , 2 ≤ j ≤ t, d0 → d1 ] 2 , A → A1 ] 1 , for all A ∈ N2 .

All symbols “start to count”, from 1 to t + 1. Note that during this counting no symbol from the skin membrane can enter any of the inner membranes. 5. [ [ [ [ Xi,k → Xi,k+1 ] 2 , for all X ∈ N1 , 2 ≤ i ≤ t, 1 ≤ k ≤ i ? 1, Bj,k → Bj,k+1 ] 2 , for all A ∈ N2 , 2 ≤ j ≤ t, 1 ≤ k ≤ j ? 2, dk → dk+1 ] 2 , for all 1 ≤ k ≤ t, Ak → Ak+1 ] 1 , for all A ∈ N2 , 1 ≤ k ≤ t. 7

The rules used during the counting. 6. [ Bj,j?1 ] 2 → Bj , for all B ∈ N2 , 2 ≤ j ≤ t, [ Xi,i → #] 2 , for all X ∈ N1 , 2 ≤ i ≤ t. Only the symbol from N2 can dissolve membrane 2, and this happens in the moment when it is going to get a subscript j, k with j = k. If i < j, then X gets the subscript i, i before dissolving the membrane, hence the trap-symbol is introduced. This will also happen if no symbol from N2 were present in this membrane. If, however, j < i, then the membrane will be “prematurely dissolved”, and a symbol Xi,k with i > k will be left free in the skin region, introducing # there – see the rules below. In this way we check that the symbols Xi,?1 , Bj,0 introduced in the membrane have i = j, hence correspond to the same matrix of G. 7. [ [ [ [ [ Xi,k → #] 1 , for all X ∈ N1 , 2 ≤ i ≤ t, 1 ≤ k ≤ i ? 1, dk → #] 1 , for all k ≤ t, c1 → λ] 1 , Xi,i → Yi+1 ] 1 , Bi → hi+1 (x)] 1 , for mi : (X → Y, B → x), Y ∈ N1 ∪ {f }.

The ?rst rule ensures the correct simulation of the matrix mi , the second one ensures the fact that in the third step d0 was sent to the second membrane with label 2, while the last two rules actually simulate the matrix. Note that in the meantime, all symbols from N2 present in the skin have continued to increase their subscript – and the same with dk from the second membrane 2. The symbol Y and the nonterminals from x are introduced with the subscript equal to the subscripts of all these symbols from the skin membrane, in order to continue together to count to t + 1; this is important for the synchronization of the system. ? 8. [ Yt+1 → Y ] 1 , for all Y ∈ N1 ∪ {f }, ? [ At+1 → A] 1 , for all A ∈ N2 , [ dt+1 → c] 2 . When all symbols get the subscript t+1, we can return to a con?guration similar to the initial one, with all nonterminals barred, and with c in membrane 2, hence we can iterate the process, and simulate another matrix of G. ? ? 9. f [ ] 2 → [ f ] 2 , ? ? [ f]2 → f, [ Ai,k → #] 1 , for all A ∈ N2 , 1 ≤ k < i ≤ t, [ dt+1 → λ] 2 , [ # → #] s , s = 1, 2. After using a terminal matrix of G, we have to also remove the symbols d and c, and, furthermore, no symbol from N2 should be present in the system. Assume ? ? that this is not the case, hence we have at least f , A in the skin membrane, for ? some A ∈ N2 , and c in membrane 2. If f enters membrane 2, then c introduces 8

? ? #, hence membrane 2 should be divided, while f waits and A is replaced by A. ? enters the ?rst membrane 2 – the second one should be used In the next step f ? by c2 , as we have seen above – and A becomes A . Now, if f dissolves membrane 2, then A should pass to A and then starts to count; if A enters membrane 2, ? then f waits, but it dissolves the membrane in the next step, and Ai,1 is released ? into the skin region, where it will introduce #. If f enters the second membrane 2 and dissolves it, then a symbol dk is released, and again we introduce # in the skin region. If no membrane is present, then A will count forever from 1 to t + 1, repeatedly. Thus, the only way to stop is to correctly simulate a terminal ? derivation in G, removing dt+1 at the same time when introducing f .) 10. [ a] 1 → [ ] 1 a, for all a ∈ T . Any terminal symbol is sent out at any time of the computation. From the previous explanations it is easy to see that ΨT (L(G)) = P s(Π), which proves the inclusion P sM AT ? P sOP (a0 , b0 , c0 , d0 , e0 ) (note that rules of all ?ve types were used). In order to see that the inclusion is proper, consider the system Π = ({a}, {1, 2}, [ [ ] 2 ] 1 , λ, a, {[ a → aa] 2 , [ a] 2 → a, [ a] 1 → [ ] 1 a}), which generates the set P s(Π) = {(2n ? 1) | n ≥ 1} ∈ P sM AT . / We do not know whether the previous result can be improved by avoiding the use of some types of rules, or – more interesting – strengthening it to a characterization of P sRE. Because we believe that such a characterization is not possible, a related question is to consider further ingredients which can increase the power. A possibility is to use a priority relation among rules, of a weak type (a general priority is known to lead to universality, see [9]); for example, we can use always the rules of some type with priority over the rules of another type (e.g., always the communication having priority on dividing a membrane). This possibility, as well as the general problem concerning the size of the family P sOP (a0 , b0 , c0 , d0 , e0 ), remains as a task for the reader, and we consider in the next section another way to “pay” for not using polarizations: changing the labels of membranes.

4

The Power of Changing Labels

Rules of types (a), (b), (c) 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] h1 → [ b] h2 [ c] h3 , with a, b, c ∈ O, e1 , e2 , e3 ∈ {+, ?, 0}, and h1 , h2 , h3 ∈ H, 1 2 3 and they have been called of type (e ). We extend this idea and this notation to rules of types (e0 ), (b0 ), and (c0 ): their primed versions indicate the fact that the labels can be changed. Speci?cally, these rules are of the following forms: 9

e e e

(e0 ) [ a] h1 → [ b] h2 [ c] h3 , where a, b, c ∈ O and h1 , h2 , h3 ∈ H, (b0 ) a[ ] h1 → [ b] h2 , where a, b ∈ O and h1 , h2 ∈ H, (c0 ) [ a] h1 → [ ] h2 b, where a, b ∈ O and h1 , h2 ∈ H. The families of sets of vectors of natural numbers generated by systems using a certain combination of types of rules, with or without subscripts or superscripts, are denoted as usual, by P sOP followed by the “names” of the used types of rules. Of course, rules of type (α) or (α0 ) are stronger than rules of type (α0 ). Are these relations (“stronger/weaker”) proper? We are going to show that this seems to be the case when passing from (α0 ) to (α0 ). 4.1 Simulation Results

We start by considering the case when rules of type (e0 ) are used. They help at least for a class of systems of a restricted type. Speci?cally, we say that a P system (with active membranes and using polarizations) is of type D2S0 if its membrane structure has only two levels (depth two, hence D2) and its skin membrane never changes the polarization (hence it remains neutral as at the beginning, a fact indicated by S0). Lemma 1. Any P system of type D2S0 can be simulated by a system using rules of types (a0 ), (b0 ), (c0 ), (d0 ), (e0 ). Proof. Let us consider a system Π = (O, H, ?, w1 , . . . , wm , R) of type D2S0. We assume that the skin membrane is labeled with 1 and that this label is never used for another membrane (this can be easily achieved, by relabeling the membranes, taking into account that the skin membrane is never divided). We also assume the rules of type (b) from R (if any) labeled in a one-to-one manner with elements e e of a set B (hence we write these rules in the form r : a[ ] h1 → [ b] h2 . Consider ? also the alphabet O1 = {a1 | a ∈ O} and the morphism ? : O? ?→ O1 de?ned by ?(a) = a1 , a ∈ O. We construct the system (without polarizations) Π = (O , H , ? , w1 , . . . , wm , R ), with the following components: O = O ∪ {ai , ai , ai | a ∈ O, 1 ≤ i ≤ 5} ∪ {b2 | r : a[ ] h1 → [ b] h2 is a rule of type (b) from R} ∪ {d, $, $ , $ , #}, H = { h, e , h , e | h ∈ H, e ∈ {+, ?, 0}} ∪ {0}, ? is the membrane structure ? with each membrane with label h (and polarization 0, as it is the case at the beginning) labeled with h, 0 , and with the set R constructed as follows. 10

(r) e e

? For each rule [ a → x] h ∈ R of type (a), we introduce in R the rules: 1. [ a → ?(x)] h,e , 2. [ b1 → b1 ] h,e , [ b1 → b1 ] h ,e , 3. [ b1 → b1 ] h,e , [ b1 → b1 ] h ,e , 4. [ b1 → b] h,e , [ b1 → b] h ,e , for all b ∈ O. ? For each rule r : a[ ] h1 → [ b] h2 ∈ R of type (b), we introduce in R the rules: 1. a[ ] 2. [

h,e1 , (r) b2 ] h,e1 → [ b2 ] h ,e2 [ (r) b2 → #] h,e1 , h,e1 e e

e

→ [ b2 ]

(r)

d] 0 ,

[ 3. [ b2 → b2 $ ] h ,e2 , 4. [ b2 → b] h ,e2 , [ $ ] h ,e2 → [ $ ] h,e2 [ d] 0 . ? For each rule [ a] h1 → [ ] h2 b ∈ R of type (c), with h = 1, we introduce in R the rules: 1. [ a] h,e1 → [ b3 ] h ,e2 [ d] 0 , 2. [ b3 → b3 $] h ,e2 , 3. [ b3 ] h ,e2 → [ ] h ,e2 b3 , [ $ → $ ] h ,e2 , 4. [ b3 → b] g , for all g ∈ H , [ $ ] h ,e2 → [ $ ] h,e2 [ d] 0 . ? For each rule [ a] h → b ∈ R of type (d), we introduce in R the rules: 1. 2. 3. 4. [ [ [ [ a] h,e → [ b4 ] b4 → b4 ] h ,e , b4 → b4 ] h ,e , b4 ] h ,e → b.

e h ,e e e e

[ d] 0 ,

? For each rule [ a] h1 → [ b] h2 [ c] h3 ∈ R of type (e), we introduce in R the rules: 1. [ a] h,e1 → [ b5 ] h ,e2 [ c5 ] h ,e3 , 2. [ α5 → α5 $] h ,e , for all α ∈ O, e ∈ {+, ?, 0}, 3. [ α5 → α5 ] h ,e , for all α ∈ O, e ∈ {+, ?, 0}, [ $ → $ ] h ,e , for all e ∈ {+, ?, 0}, 11

e

e

4. [ α5 → α] h ,e , for all α ∈ O, e ∈ {+, ?, 0}, [ $ ] h ,e → [ $ ] h,e [ d] 0 , for all e ∈ {+, ?, 0}. ? Finally, for each rule [ a] 1 → [ ] 1 b of R we introduce in R the rule [ a] 1,0 → [ ] 1,0 b, ? and then, for all labels g ∈ H we introduce the rule [ # → #] g . The idea behind this construction should be visible: instead of working with e membranes with labels and polarizations, [ ] h , we work with membranes having only labels, [ ] h,e , with the polarizations “stored” as the second component of the labels; by handling labels we can then handle polarizations; the problem is that the labels are changed only by rules of type (e0 ); moreover, we have to carefully arrange the computations in Π in order not to lose the synchronization of computations in Π. The synchronization is obtained by using symbols with subscripts 1, 2, 3, 4, 5, associated with rules of R of the types (a), (b), (c), (d), (e), respectively, sometimes priming these symbols, and also using labels not only of the form h, e , but also of the form h , e . Each step of a computation in Π is simulated by four steps of a computation in Π . In the ?rst step all symbols are like in O, without subscripts or primes, and the labels of membranes are of the form h, e . After the ?rst step, all objects which can evolve by a rule in R can also evolve by a rule in R and the objects introduced in this way have subscripts; these objects have now to evolve in a well determined manner, completing the simulation of the rule in R and returning to objects from O only in the last step, the fourth one. Moreover, the simulation of rules of types (c), (d), (e) starts by using a rule of R of type (e0 ), which introduces a “main membrane” with the label of the type h , e (with the label h ∈ H primed), corresponding to the e membrane [ ] h from ? whose rule is simulated, as well as a “dummy membrane”, [ d] 0 , containing the “dummy object” d which never evolves (no rule is associated with this membrane). In the simulation of a rule of type (b) one introduces a label of type h , e in the second step. In the simulation of rules of all types (b), (c), (e) a further division is performed in the fourth step, returning the label h , e to h, e , thus making possible the simulation of another rule from R. Because the case of rules of type (b) is di?erent from the case of the other e rules, we describe it in some details. Assume that we have a membrane [ ] h1 e1 e2 where we want to use a rule r : a[ ] h → [ b] h . We start by using the rule (r) a[ ] h,e1 → [ b2 ] h,e1 . This is possible, as the symbol a and the label h, e1 are available. (In parallel with the rule r, no further rule of types (b), (c), (d), (e) can involve the same membrane, but a maximal use of rules of type (a) should be executed; this is clearly possible also in Π .) The label of the membrane was not changed, but only the symbol b got both the subscript 2 (as associated with rules of type (b)) and the superscript (r), to “remember” which rule we have to simulate. In the next step, because the label of the membrane is the same as in 12

0 0

the ?rst step, we can involve this membrane in rules of types (b), (c), (d), (e), and this would be wrong, because it does not correspond to a correct simulation of rules from R (the simulation of the rule r was not completed). This is prevented (r) by the rule [ b2 → #] h,e1 : because of the maximal parallelism, it has to be applied, and this will lead to a non-halting computation. Therefore, we have to (r) use the rule [ b2 ] h,e1 → [ b2 ] h ,e2 [ d] 0 , which continues the correct simulation: the label was changed to h , e2 , hence no new simulation can be started in this membrane (while the rules of R corresponding to rules of type (a) from R can be applied also in the presence of this label). We continue in a deterministic way with the rule [ b2 → b2 $ ] h ,e2 (step 3 of the simulation), and we conclude by using the rules [ b2 → b] h ,e2 , [ $ ] h ,e2 → [ $ ] h,e2 [ d] 0 , in parallel. We have returned to a con?guration as that we have started with, hence the simulation of rules from R can continue. Note the role of the superscript (r) in step 2, when it was necessary to know the new polarization e2 of the membrane, as well as the role of the special object $, primed or not, which takes care of returning the membrane to a label h, e in the fourth step of the simulation. The simulation of rules of other types than (b) is easier, in the sense that it is deterministic, no trap-object is used in order to avoid “wrong” simulations. In any moment, the objects which were sent out of the system by rules of R are also sent out of ? by the rules of R . In all this construction, it is crucial that the skin never changes its polarization (we cannot divide the skin, hence we cannot handle such a case in this framework), and that we have inside the skin only elementary membranes (neither the change of polarization of a non-elementary membrane can be handled, because we cannot divide non-elementary membranes). With these observations, we conclude that the statement in the lemma holds. In the previous construction the number of membranes with label 0 can grow arbitrarily large. We can prevent this by introducing the following rules in R : [ [ [ [ d → d ] 0, a → λ] 0 , for all a ∈ O , d ]0 → d , d → λ] 1 .

In this way, all objects from membranes with label 0 are removed, in parallel with changing d to d , in the next step the membrane is dissolved, and after that the new object d is erased. We now pass to the case where we can change the label of membranes by means of rules of type (c). Lemma 2. Any P system with rules of types (a), (b), (c), (d), (e) can be simulated by a system using rules of types (a0 ), (b0 ), (c0 ), (d0 ), (e0 ). Proof. We start again from a system Π = (O, H, ?, w1 , . . . , wm , R). Without loss of generality we assume that no membrane has the label s. We also assume all the 13

rules from R labeled in a one-to-one manner with elements of a set B. Consider ? again the alphabet O1 = {a1 | a ∈ O} and the morphism ? : O? ?→ O1 de?ned by ?(a) = a1 , a ∈ O. We construct the system (without polarizations) Π = (O , H , ? , w1 , . . . , wm , R ), with the following components: O = O ∪ {a , a1 , a1 , a1 , a1 | a ∈ O} ∪ {a(r) , a , a ,a | a ∈ O, r ∈ B} ∪ {ae | a ∈ O, e ∈ {+, ?, 0}} ∪ {$e | e ∈ {+, ?, 0}} ∪ {$, $ , #}, H = { h, e , h, e, r | h ∈ H, e ∈ {+, ?, 0}, r ∈ B} ∪ {s}, ? is obtained from the membrane structure ? by using a new membrane, with label s, to enclose the membrane structure ? (this is the skin membrane of ? ) and each membrane in ? with label h being labeled with h, 0 , and with the set R constructed as follows. ? For each rule [ a → x] h ∈ R of type (a), we introduce in R the rules: 1. [ a → ?(x)] h,e , 2. [ b1 → b1 ] h,e , [ b1 → b1 ] h,e,r , 3. [ b1 → b1 ] h,e , [ b1 → b1 ] h,e,r , 4. [ b1 → b1 ] h,e , [ b1 → b1 ] h,e,r , 5. [ b1 → b] h,e , [ b1 → b] h,e,r , for all b ∈ O, and r ∈ B. ? For each rule r : a[ ] h1 → [ b] h2 ∈ R of type (b), we introduce in R the rules: 1. a[ ] 2. [ b

(r) h,e1 e e e (r) (r) (r)

→ [ b(r) ] →[ ]

h,e1

, b (r) ,

]

h,e1

h,e2 ,r

4. [ b(r) → b $] h,e2 ,r , 5. [ b → b] h,e2 ,r , [ $] h,e2 ,r → [ ] h,e2 $ .

e

[ b(r) → #] g , for all g ∈ { h, e | h ∈ H, e ∈ {+, ?, 0}}, 3. b (r) [ ] h,e2 ,r → [ b(r) ] h,e2 ,r ,

? For each rule r : [ a] h1 → [ ] h2 b ∈ R of type (c), we introduce in R the rules:

e

14

1. [ a] h,e1 → [ ] h,e2 ,r b (r) , 2. b (r) [ ] h,e2 ,r → [ b(r) ] h,e2 ,r , 3. [ b(r) → b

(r) (r) (

]

h,e2 ,r

,

4. [ b → b r)] h,e2 ,r , 5. [ b (r)] h,e2 ,r → [ ] h,e2 b. ? For each rule r : [ a] h → b ∈ R of type (d), we introduce in R the rules: 1. [ a] h,e → [ ] h,e,r b (r) , 2. b (r) [ ] h,e,r → [ b(r) ] h,e,r , 3. [ b(r) → b 4. [ b 5. [ b

(r) (r) (r) e

]

h,e,r

, ,

→b ]

h,e,r

(r)

]

h,e,r

→ b.

e e e

? For each rule r : [ a] h1 → [ b] h2 [ c] h3 ∈ R of type (e), we introduce in R the rules: [ a] h,e1 → [ ] h,e1 ,r a (r) , a (r) [ ] h,e1 ,r → [ a(r) ] h,e1 ,r , [ a(r) ] h,e1 ,r → [ be2 ] h,e1 ,r [ ce3 ] h,e1 ,r , [ be2 → b $e2 ] h,e1 ,r , [ ce3 → c $e3 ] h,e1 ,r , 5. [ b → b] h,e1 ,r , [ c → c] h,e1 ,r , [ $ei ] h,e1 ,r → [ ] h,ei $ , for i = 2, 3. 1. 2. 3. 4. ? Finally, for the output of the result, we introduce in R the rules [ a] s → [ ] s a, for all a ∈ O, ? and then, for all labels g ∈ H we introduce the rule [ # → #] g . The idea is the same as in the proof of the previous lemma: instead of working e with membranes with labels and polarizations, [ ] h , we work with membranes having only labels, [ ] h,e , with the polarizations “stored” as the second component of the labels. This time, one step of a computation in Π is simulated by ?ve steps in Π , controlled mainly by the superscripts (r) of symbols from O , which identify the rule which is simulated. Note that r appears also in labels of the form h, e, r , which correspond to labels of the form h , e in the previous proof (in the sense that these labels are always returned to labels h, e only in the ?fth step of simulating a rule of types (b, ), (c), (d), (e), thus making possible the simulation of another rule). Again, we use the trap-symbol only for ensuring the correct simulation of rules of type (b), which is di?erent from the case of the other rules, but we do 15

not enter here into details. With the experience of the previous proof, the reader should be able to see how the computations in Π develop. In all cases of rules di?erent from type (a) it is important to note that we change the label of the membrane by sending out of it an object, one copy of which should come back in the next step. In order to ensure this, both the membrane “remembers” which kind of objects should come back, because we have r in the label, and the object “remembers” which kind of membranes has to enter, because it has the superscript (r). Because of the fact that the number of copies of objects b (r) is equal to the number of membranes which send out the objects b (r) and because of parallelism, each membrane which previously send out an object b (r) will now contain an object b(r) . At any moment, the objects which were sent out of the system by rules of R are also sent out of ? by the rules of R . Consequently, the two systems Π and Π are equivalent. In the construction above, except for the new skin membrane, that with the label s, the membrane structure remains the same (only the labels are changed during computations). 4.2 Universality Consequences

From Theorem 1 (Theorem 7.2.1 in [9]) we know that systems with rules of types (a), (b), (c) are Turing complete. The proof from [9] (recalled there from [5]) uses only three membranes, arranged in two levels – hence from this point of view the premises of both lemmas from the previous section are satis?ed. Unfortunately, that proof changes the polarization of the skin membrane. A close examination of the proof shows, however, that this change is done only once, in the end of the computation. More precisely, one starts from a matrix grammar G with appearance checking in the binary normal form. The terminal matrix (X → λ, A → x) of the grammar is replaced by a matrix of the form (X → f, A → x), where f is a new symbol. The idea is that when the symbol f is introduced (actually, it is introduced as f ), the derivation G should be terminal, hence no further rule of it should be simulated in the constructed P system. To this aim, f is sent out of the system, changing the polarization of the skin membrane from 0 to +. If the derivation in G was not terminal, then in the positively polarized skin, each nonterminal A of G evolves by a rule A → #, thus preventing the halting of the computation (we also have there the rule # → #). This control of the correct termination of the simulation can be achieved without changing the polarization of the skin membrane, by introducing one additional membrane, with label 4, at the same level with membranes 2 and 3, removing the rules which change the polarization of the skin or use its positive polarization, and considering the following new rules: f [ ]4 → [ f ]4 , + + A[ ] 4 → [ #] 4 , for all nonterminals A of G, + [ # → #] 4 . 16

0 +

The role of (the positive polarization of) the skin is played now by (the positive polarization of) membrane 4. In this way we get a system which is of type D2S0, hence we can conclude: Theorem 3. P sOP (a0 , b0 , c0 , e0 ) = P sOP (a0 , b0 , c0 ) = P sRE. The equalities follow from Lemmas 1, 2, from the previous change of the proof of Theorem 1, and from the observation that in the proof of Lemma 1 we use rules of type (d0 ) only for simulating rules of type (d), while in the proof of Lemma 2 we use rules of types (d0 ), (e0 ) only in the simulation of rules of types (d), (e), respectively. 4.3 Direct Universalities

Because we do not have a simulation lemma also for the case of using rules of type (b0 ) for changing the labels of membranes, the universality does not follow for this case as for the other cases, and that is why we look for a direct proof of universality. Rather instructively, the proof is much simpler than when we use polarizations but not label changing features, and this is due to a tricky possibility to use the labels of membranes. Theorem 4. P sOP (a0 , b0 , c0 ) = P sRE. Proof. Consider a matrix grammar G = (N, T, S, M, F ) with appearance checking, in the binary normal form, hence with N = N1 ∪ N2 ∪ {S, #} and with the matrices of the four forms introduced in Section 3. Assume that all matrices are injectively labeled with elements of a set B. Replace the rule X → λ from matrices of type 4 by X → f , where f is a new symbol. We construct the P system of degree 2 Π = (O, H, [ [ ] Xinit ] 1 , w1 = cAinit , wXinit = λ, R), O = T ∪ N2 ∪ {Am | A ∈ N2 , m ∈ B} ∪ {c, c , c , c1 , c2 , c3 , c4 , c5 , #}, H = N1 ∪ {Xm | X ∈ N1 , m ∈ B} ∪ {1, f }, and the set R containing the following rules. We present them in blocks as used for simulating matrices of G, thus also having clear the way the system Π works. The simulation of a matrix m : (X → Y, A → x), with X ∈ N1 , Y ∈ N1 ∪{f }, is done in three steps, using the next rules: 1. A[ ] X → [ Am ] Ym , [ c → c ] 1, 2. [ Am ] Ym → [ ] Ym Am , [ c → c ] 1, 3. [ Am → xc] 1 , c [ ] Ym → [ c ] Y . 17

The ?rst rule of the matrix is simulated by the change of the label of the inner membrane, and the correctness of this operation is obvious (one cannot simulate one rule of the matrix without simulating at the same time also the other rule). The simulation of a matrix m : (X → Y, A → #), with X, Y ∈ N1 and A ∈ N2 , is done in ?ve steps, using the next rules: 4. c[ ] X → [ c1 ] Ym , 5. [ c1 → c2 ] Ym , A[ ] Ym → [ #] f , 6. [ c2 ] Ym → [ ] Ym c3 , 7. [ c3 → c4 c5 ] 1 , 8. [ c4 → c] 1 , c5 [ ] Ym → [ c ] Y . While the membrane with label X is used by object c, no other rule can be used. In the next step, if any copy of A is present, then it introduces the trap-object # and the computation never stops. If no A is present, then the objects cj evolve, returning the label of the membrane to Y and introducing the auxiliary object c, for iterating the procedure. We also consider the following rules: 9. A[ ] f → [ #] f , for all A ∈ N2 , 10. [ # → #] f , 11. [ a] 1 → [ ] 1 a, for all a ∈ T . The equality ΨT (L(G)) = P s(Π) easily follows from the above explanations. A similarly easy direct proof of universality can be given for systems using rules of the types (a0 ), (b0 ), (c0 ). We leave this task to the reader, and we give here the direct universality proof for the case of using rules of type (e0 ): this time the surprise is twofold – not only the construction is trivial, but also only rules of types (a0 ), (c0 ), and (e0 ) are used, thus improving the ?rst equality from Theorem 3. Theorem 5. P sOP (a0 , c0 , e0 ) = P sRE. Proof. Consider again a matrix grammar G = (N, T, S, M, F ) with appearance checking, in the binary normal form, with the notations and the assumptions from the previous proof, and construct the P system of degree 2 Π = (O, H, [ [ ] Xinit ] 1 , w1 = λ, wXinit = c0 Ainit , R), O = T ∪ N2 ∪ {Am | A ∈ N2 , m ∈ B} ∪ {c, c , c0 , c1 , c2 , d, #}, H = N1 ∪ {Xm | X ∈ N1 , m ∈ B} ∪ {0, 1, f }, and the set R containing the following rules. The simulation of a matrix m : (X → Y, A → x), with X ∈ N1 , Y ∈ N1 ∪{f }, is done in three steps, using the next rules: 18

1. [ A] X → [ Am ] Ym [ d] 0 , 2. [ Am → xc] Ym , 3. [ c] Ym → [ c ] Y [ d] 0 . Again the ?rst rule of the matrix is simulated by the change of the label of the inner membrane (the “dummy” object d and membrane 0 play no further role). The simulation of a matrix m : (X → Y, A → #), with X, Y ∈ N1 and A ∈ N2 , is done also in three steps, using the next rules: 4. [ c0 ] X → [ c1 ] Ym [ d] 0 , 5. [ c1 → c2 ] Ym , [ A → #] Ym , 6. [ c2 ] Ym → [ c0 ] Y [ d] 0 . While the membrane with label X is used by object c0 , no other rule can be used. In the next step, if any copy of A is present, then it introduces the trap-object # and the computation never stops. If no A is present, then the objects cj evolve, returning the label of the membrane to Y and introducing the auxiliary object c0 , for iterating the procedure. We also consider the following rules: 7. 8. 9. 10. [ [ [ [ A → #] f , for all A ∈ N2 , # → #] h , for all h ∈ H, a] f → [ ] f a, a] 1 → [ ] 1 a, for all a ∈ T .

The equality ΨT (L(G)) = P s(Π) is again obvious. Remark 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 (e0 ) are su?cient to reach universality for membrane systems with internal output. 4.4 E?ciency

As we have noticed above, the proofs of Lemmas 1, 2 do not preserve the determinism of the simulated systems; more precisely, the constructed systems do not always halt, but any “wrong” step with respect to the starting system will lead to an endless computation. Such a behavior is not accepted in solving decidability problems with P systems, neither in the deterministic manner from [11], nor in the slightly more relaxed framework of [9], where the nondeterminism is allowed, providing that the system is con?uent (all branches of a computation eventually reach a unique con?guration), and always halts. However, as somewhat expected, P systems without polarization, but with the possibility of changing the label of membranes (by means of rules of types (c0 ) and (e0 )) can solve NP-complete problems in linear time. This is illustrated below, with direct proofs, for SAT, the typical problem used in such cases. 19

Before giving these proofs, it is worth noticing that rules of types (a0 ), (e0 ) su?ce in order to generate all 2n truth assignments for n variables from a propositional formula. Speci?cally, let us consider a (non-skin) membrane [ ] 0 where we have the objects d1 and a1 , and also consider the following rules: G1 [ di → ai+1 di+1 ] 0 , 1 ≤ i < n, G2 [ ai ] 0 → [ ti,i ] 0 [ fi,i ] 0 , 1 ≤ i ≤ n, G3 [ ti,j → ti,j+1 ] 0 , [ fi,j → fi,j+1 ] 0 , 1 ≤ i ≤ j < n. In each step, one “expands” one variable, starting with x1 and ending with xn , deterministically. The truth values ti,j , fi,j of variables xi have associated second subscripts j specifying the step, so that, in n steps the membrane [ d1 a1 ] 0 is divided in 2n membranes, each of them containing a multiset of the form dn v1 v2 · · · vn , where vi ∈ {ti,n , fi,n }. In a way which will be used in the proof of the Theorem 9, by using the rules of types (a0 ), (e0 ) only, during the generation of truth assignments we can also check which clauses are satis?ed by the truth assignments – we skip the details here. Unfortunately, we do not see any way to check the truth value of the whole formula for these truth assignments by using only rules (a0 ), (b0 ), (c0 ), (d0 ), (e0 ), and that is why we use below also rules for changing the labels. A rigorous framework for dealing with complexity matters in our area is that of recognizing P systems, which we introduce here following [10]. First, let us consider P systems with input, which will allow the input of a multiset encoding a decision problem, in a special membrane. Such a device is a tuple (Π, V, i0 ), where: – Π is a usual P system, with the alphabet of objects O and initial multisets w1 , · · · , wm (associated with membranes labelled by 1, · · · , m, respectively). – V is an (input) alphabet strictly contained in O and such that w1 , · · · , wm are multisets over O ? V . – i0 ∈ {1, 2, . . . , m} is the label of a distinguished membrane (of input). If w is a multiset over V , then the initial con?guration of (Π, V, i0 ) with input w is (?, w1 , · · · , wm ), where wi = wi for i = i0 , and wi0 = wi0 ∪ w. The computations of a P system with input are de?ned in a natural way, the only change is that the initial con?guration is obtained by adding the input multiset w over V to the initial con?guration of the system Π. Then, a recognizing P system is a P system with input, (Π, V, i0 ), such that: 1. The alphabet O of Π contains two distinguished elements yes, no. 2. All computations of the system halt. 3. If C is a computation of Π, then either the object yes or the object no (but not both) is sent out to the environment, and only in the last step of the computation. 20

We say that C is an accepting (respectively, rejecting) computation if the object yes (respectively, no) appears in the environment in the halting con?guration of C. Given a decision question X, we say that it can be solved in polynomial (linear) time by recognizing P systems (with active membranes in our case) if, informally speaking, we can construct in polynomial time a family of recognizing P systems (Π, V, i0 )n , n ∈ N, associated with the sizes n of instances X(n) of the problem, such that, after introducing an encoding of X(n) via an input multiset, 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. Note that always we have an answer, one of yes and no, but we have said nothing about the way the computations evolve, the only restriction we impose is that all of them halt (in a number of steps bounded by a known function). That is why we say that such systems are con?uent (they may be non-deterministic, but the answer is obtained in a ?nite time irrespective of the possible branchings of the computations). The deterministic systems, where no branching is possible, are a particular case of con?uent systems. With these prerequisites, we now pass to giving the announced e?ciency results. Theorem 6. P systems with rules of types (a0 ), (b0 ), (c0 ), (e0 ) can solve SAT in linear time in a con?uent 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 ( n, m ) = {xi,j , xi,j | 1 ≤ i ≤ m, 1 ≤ j ≤ n}. The object xi,j represents the variable xj appearing in the clause Ci without negation, and object xi,j represents the variable xj appearing in the clause Ci with 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 (Π( n, m ), V ( n, m ), 2) with: Π( n, m ) = (O( n, m ), H, ?, w1 , w2 , w7 , R), O( n, m ) = {xi,j , xi,j | 1 ≤ i ≤ m, 0 ≤ j ≤ n} ∪ {di | 0 ≤ i ≤ 2n + 2m + 5} ∪ {ci | 1 ≤ i ≤ m} ∪ {e, f0 , f1 , yes, no}, 21

? = [ [ ] 2[ ] 7] 1, w1 = λ, w2 = w7 = d0 , H = {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 → [ di ] 3 [ di ] 4 , 0 ≤ i < n, G2 [ di ] l → [ di+1 ] 2 [ d0 ] 1 , l ∈ {3, 4}, 0 ≤ i < n, G3 [ dn ] 2 → [ d0 ] 5 [ d0 ] 1 . In 2n + 1 steps, 2n membranes with label 5 are created, corresponding to the truth assignments of the variables x1 , · · · , xn . During this process, the object di inside the membrane with label 3 corresponds to the true value of variable xi+1 , and the object di inside the membrane with label 4 corresponds to the false value of variable xi+1 . The created membranes with label 1 are dummy membranes: no rule associated with them is applied; this allows us to change the membrane labels during the computation. G4 [ [ G5 [ [ G6 [ [ xi,j xi,j xi,0 xi,0 xi,0 xi,0 → xi,j?1 ] 2 , → xi,j?1 ] 2 , 1 ≤ i ≤ m, 1 ≤ j ≤ n, → ci ] 3 , → λ] 4 , 1 ≤ i ≤ m, → λ] 3 , → ci ] 4 , 1 ≤ i ≤ m.

The labels of the created membranes toggles between 2 at even steps and 3 or 4 at odd steps. Every object xi,j of the input evolves to xi,0 in 2j ? 1 steps. Then, it evolves to ci in membranes where true value was chosen for xj (recall that xi,j = true satis?es clause Ci ) and is erased in membranes where false value was chosen for xj . Similarly, xi,j changes to ci if xj = false and is erased if xj = true. After 2n + 1 steps, the membranes with label 5 will represent all possible truth assignments of the variables in β. Every such membrane will contain d0 and the objects representing the clauses satis?ed by the present truth assignment. Checking phase C1 [ c1 ] 5 → [ c0 ] 6 [ d0 ] 1 , C2 [ ci → ci?1 ] 6 , 1 ≤ i ≤ m, C3 [ di ] 6 → [ di+1 ] 5 [ d0 ] 1 , 0 ≤ i < m, [ c0 → λ] 5 , C4 [ dm → ef0 ] 5 . A membrane with label 5 where object c1 appears will change the label to 6 (recall that no rule is ever applied in membranes with label 1 created by division). In a membrane with label 6, the subscripts of all objects cj are decremented by one, and at the same time the subscript of di is incremented by one and the label of membrane changes back to 5. 22

If in the beginning of the checking phase c1 , · · · , ci are present (0 ≤ i < m?1), but ci+1 is absent, then the evolution of the membrane ?nishes after 2i steps with label 5, with di and without c1 . If all objects ci , 1 ≤ i ≤ m, are present in the beginning of the checking phase, then after 2m steps they will all be rewritten into c0 , and d0 will evolve into dm (and into ef0 in one more step). C5 [ e] 5 → [ ] 5 e, [ f0 → f1 ] 5 , C6 e[ ] 7 → [ e] 7 , [ f1 ] 5 → [ d2m+2n+4 ] 6 [ d0 ] 1 , C7 e[ ] 6 → [ e] 6 . If β has solutions (suppose β has s solutions, 1 ≤ s ≤ 2n ), then at step 2n + 2m + 3, every membrane corresponding to a solution of β ejects e in the skin region, and at the same time f0 changes to f1 . At step 2n + 2m + 4, one copy of e enters the membrane with label 7, and s membranes change label from 5 to 6 by rule [ f1 ] 5 → [ e] 6 [ d0 ] 1 . At step 2n + 2m + 5, s ? 1 copies of e enter in s ? 1 membranes of the s + 1 membranes with labels 6 and 7. If β has no solution, then no object e enters membrane labeled 7. O1 O2 O3 O4 O5 O6 O7 Output phase [ di → di+1 ] 7 , 0 ≤ i ≤ 2m + 2n + 4, [ e] 7 → [ yes] 6 [ d0 ] 1 , [ yes] 6 → [ ] 6 yes, [ yes] 1 → [ ] 1 yes, [ di → λ] 6 , i ∈ {2n + 2m + 4, 2n + 2m + 5} [ d2n+2m+5 ] 7 → [ ] 7 no, [ no] 1 → [ ] 1 no.

If β has solutions, then at step 2n + 2m + 4 the membrane with label 7 receives a copy of e by rule C6. In this case, rule O2 will be applied either at step 2n+2m+4 or at step 2n + 2m + 5 (this can happen if s > 1 and rule C6 is applied at step 2n + 2m + 4), changing the label of the membrane from 7 to 6. It will take two more steps to eject object yes in the skin and then into the environment. If β has no solutions, then after step 2n + 2m + 5 the membrane with label 7 remains with label 7 and then rule O6 is applied, ejecting object no into the skin and then into the environment. If β has at least two solutions, then the behavior of this system is not deterministic: in step 2n + 2m + 4 either one of the rules C6 and O2 can be applied to the membrane with label 7 (applying C6 in step 2n + 2m + 4 results in one extra copy of e in membrane with label 7 and one copy of e missing in some membrane with label 6). However, the system is con?uent: in either case mentioned above, after at most three further steps, the system produces the output yes and halts in the same con?guration (the membrane with label 7 changes its label to 6 and the counter d2n+2m+4 or d2n+2m+5 is erased). From this point of view, using rules of type (c0 ) allows to obtain a stronger result: 23

Theorem 7. P systems with rules of types (a0 ), (c0 ), (e0 ) can solve SAT in linear time in a 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 β is encoded as a multiset w over Σ( n, m ) in the same way as in the previous proof. For given (n, m) ∈ N2 , we construct a recognizing P system (Π( n, m ), V ( n, m ), 2), with Π( n, m ) = (O( n, m ), H, ?, w1 , w2 , R), O( n, m ) = Σ( n, m ) ∪ {di | 0 ≤ i ≤ 4n + 2m + 4} ∪ {ei | 0 ≤ i < n} ∪ {ci | 1 ≤ i ≤ m} ∪ {a, t, f, u, v, yes, no}, ? = [ [ ] 2] 1, w1 = w2 = d0 , H = {1, 2, 3, 4, 5, 6, 7}, and the following rules (we also explain the construction here): Generation phase G1 [ di → ei au] 2 , 0 ≤ i < n, G2 [ a] 2 → [ t] 2 [ f ] 2 , G3 [ t] 2 → [ ] 3 a, [ f ] 2 → [ ] 4 a, G4 [ ei → di+1 ] l , l ∈ {3, 4}, 0 ≤ i < n, G5 [ u] l → [ ] 2 a, l ∈ {3, 4}. In 4n steps, 2n membranes are created, corresponding to the truth assignments of the variables x1 , · · · , xn . During this process, object di inside the membrane with label 3 corresponds to the true value of variable xi+1 , and object di inside the membrane with label 4 corresponds to the false value of variable xi+1 . Object a is used to choose the truth assignment of variables, and object u is used to change the membrane label back to 2. G6 [ [ G7 [ [ G8 [ [ xi,j xi,j xi,1 xi,1 xi,1 xi,1 → xi,j?1 ] l , → xi,j?1 ] l , 1 ≤ i ≤ m, 1 < j ≤ n, l ∈ {3, 4}, → ci ] 3 , → λ] 4 , 1 ≤ i ≤ m, → λ] 3 , → ci ] 4 , 1 ≤ i ≤ m.

The label of the created membranes is 2 and then changes to 3 or 4 at steps 4i + 3, 0 ≤ i < n. Every object xi,j of the input evolves to xi,1 in 4(i ? 1) 24

steps. Then, it evolves to ci in membranes where true value was chosen for xj (recall that xi,j = true satis?es clause Ci ) and is erased in membranes where false value was chosen for xj . Similarly, xi,j changes to ci if xj = false, and is erased if xj = true. G9 [ dn → dn+1 v] 2 , G10 [ v] 2 → [ ] 5 a, [ dn+1 → d0 u] 2 . After step 4n + 2, the membranes with label 5 will represent all possible truth assignments of the variables in β. Every such membrane will contain d0 , u, and the objects representing the clauses satis?ed. C1 C2 C3 C4 C5 Checking phase [ ci → ci?1 ] 5 , 1 ≤ i ≤ m, [ u] 5 → [ ] 6 a, [ c0 ] 6 → [ ] 5 a, [ di → di+1 u] 6 , 0 ≤ i < m ? 1, [ dm?1 → dm ] 6 .

By expelling object u, membrane changes label from 5 to 6. At the same time the subscripts of all objects cj are decremented by one. A membrane with label 6 where object c0 appears will change the label back to 5. At the same time the subscript of di is incremented by one and u is reproduced (except for i = m ? 1). If in the beginning of the checking phase c1 , · · · , ci are present (1 ≤ i < m), but ci+1 is absent, then after 2i + 1 steps rule C3 will no longer be applicable and the membrane will have label 6, no object c0 and will never change the label again. After m + i + 1 steps from the beginning of the checking phase the membrane will stop evolving. If all objects ci , 1 ≤ i ≤ m, are present in the beginning of the checking phase, then after 2m steps they will all be erased, d0 will evolve into dm and the membrane label will be 5. O1 O2 O3 O4 Output phase [ dm ] 5 → [ ] 5 yes, [ yes] 1 → [ ] 7 yes, [ di → di+1 ] 1 , 0 ≤ i ≤ 4n + 2m + 3, [ d4n+2m+4 ] 1 → [ ] 1 no.

At step 4n + 2m + 3, every membrane corresponding to a solution of β expels yes in the skin region, and in the next step one copy of yes (if any) is ejected into the environment, changing the label of the skin from 1 to 7. If β has no solutions, then after step 4n + 2m + 4 the skin membrane remains with label 1 and then rule O4 is applied, ejecting the object no into the environment. 4.5 Parallel Communication

In P systems with active membranes, the evolution rules (those of type (a)) are typically considered as only using objects, while the communication, dissolution 25

and division rules as using both objects and rules, and hence cannot be applied in parallel, because a con?ict could appear as a result of a simultaneous application of rules changing membrane polarizations (or labels) in a di?erent way. However, if we forbid the communication operations to change labels (type (b0 ) or (c0 )), then we could regard them as not using membranes and apply them in parallel, like the evolution rules, as is done, for instance, in the symport/antiport P systems in [7] and in P systems with boundary rules in [2]. Consider rules of the following types (subscript p means parallel application): (b0p ) a[ ] h → [ b] h , where a, b ∈ O and h ∈ H, (c0p ) [ a] h → [ ] h b, where a, b ∈ O and h ∈ H. P systems with membrane division with changing labels, and with parallel application of both evolution rules and communication rules of type (b0 ) turn out to be able to solve SAT in linear time in a deterministic way (thus improving from this point of view the result in Theorem 6. The universality of systems with parallel communication remains as an open question. Theorem 8. P systems with rules of types (a0 ), (b0p ), (c0 ), (e0 ) can solve SAT in linear time in a deterministic way. Proof. Following the generation phase and rules C1–C3 in Theorem 6, we replace the remaining part of the construction with: C4 [ dm ] 5 → [ ] 5 e, C5 e[ ] 7 → [ e] 7 . At step 2n + 2m + 2, every membrane corresponding to a solution of β ejects e in the skin. At step 2n + 2m + 3, all objects e move in parallel into a membrane with label 7. C6 C7 C8 C9 [ [ [ [ [ e] 7 → [ yes] 1 [ d0 ] 1 , yes] 1 → [ ] 1 yes, di → di+1 ] 7 , 0 ≤ i ≤ 2n + 2m + 3, d2n+2m+4 ] 7 → [ ] 7 no, no] 1 → [ ] 1 no.

If β has a solution, then we replace one copy of e with yes, changing the label from 7 to 1, send yes out of that membrane and then eject it in the environment. Otherwise, after step 2n + 2m + 4 the membrane with label 7 will not change its label, so no will be sent out of it and then ejected in the environment. Remark 2. In Theorem 7, no rules of type (b0 ) were used, so its statement remains valid also for parallel communication “in” (rules of type (b0p )). 26

5

Solving SAT Without Polarizations and Without Changing Labels

In the brute-force algorithms as those in Section 4.4, the ?rst phase produces all 2n truth assignments for the n variables used and the list of clauses satis?ed. As we have noticed at the beginning of Section 4.4, this can be done without using polarizations and without using the label changing possibilities. Actually, rules of types (a0 ) and (e0 ) su?ce. The second phase is to check whether there exists a membrane containing a given set of symbols. If the second phase started from a special membrane structure (of a form we will see below: with each truth assignment separately enclosed in m membranes embedded in each other, corresponding to the m clauses of a formula – see Fig. 1 for a pictorial representation), then one could solve the problem without polarizations and without changing labels, moreover, only using rules of types (a0 ), (c0 ), and (d0 ). So, the problem remains to produce the membrane structure of this “special” form – and this can be achieved by using non-elementary membrane division rules without polarizations and without changing the labels of membranes. The rules we are using will be of the form (f0 ) [ [ ] i [ ] j ] k → [ [ ] i ] k [ [ ] j ] k , where i, j, k are labels. The meaning of such a rule is that if two membranes with labels i, j are placed inside a membrane with label k, then the membrane k is divided so that one of the new membranes k contains membrane i and the other one contains membrane j; all membranes and objects placed inside membranes i and j, as well as all membranes and objects from membrane k placed outside membranes i and j, are reproduced in the new copies of membrane k. As usual, the membranes di?erent from i, j, k (those not involved in this rule) evolve in the standard nondeterministic maximally parallel manner. Rules for dividing non-elementary membranes are already known to be very powerful – illustration can be found in, e.g., [1, 14]. As we will see immediately, they are powerful even in the restricted case where no polarization is used and the labels of membranes are not changed. However, the solution we give to SAT in this framework is semi-uniform in the sense that the P system we construct starts from a given instance of the problem (not from the size of the instance, as in the uniform case); however, the construction takes a polynomial time, hence it is “honest” from this point of view. Theorem 9. P systems with rules of types (a0 ), (c0 ), (d0 ), (e0 ), (f0 ), constructed in a semi-uniform manner, can solve SAT in linear time in a 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 . 27

The instance β of SAT will be encoded in the rules of the P system by multisets vj and vj of symbols, corresponding to the clauses satis?ed by true and false assignment of xj , respectively: vj = {ci | xj ∈ {yi,k | 1 ≤ k ≤ li }, 1 ≤ i ≤ m}, 1 ≤ j ≤ n, vj = {ci | ?xj ∈ {yi,k | 1 ≤ k ≤ li }, 1 ≤ i ≤ m}, 1 ≤ j ≤ n. We construct the P system Π = (O, H, ?, w0 , · · · , wm+3 , R), with O = {di | 0 ≤ i ≤ 2n + 2m + 2} ∪ {ai , ti , fi | 1 ≤ i ≤ n} ∪ {ci | 0 ≤ i ≤ m} ∪ {yes, no}, ? = [ [ · · · [ [ ] 0 ] 1 · · · ] m+2 ] m+3 , w0 = wm+1 = d0 , wi = λ, i ∈ {0, m + 1}, / H = {0, · · · , m + 3}, and the following rules (we accompany them with explanations about their use): Generation phase G1 [ d2i → ai+1 d2i+1 ] 0 , for all 0 ≤ i < n, and [ d2i?1 → d2i ] 0 , for all 1 ≤ i ≤ n, [ d2n+i → d2n+i+1 ] 0 , 0 ≤ i < m. We count to 2n + m, which is the time needed for producing all 2n truth assignments for the n variables, as well as membrane sub-structures which will examine the truth value of formula β for each of these truth assignments; this counting is done in the central membrane; moreover during the ?rst n odd steps, symbols a1 , · · · , an are subsequently produced. G2 [ ai ] 0 → [ ti ] 0 [ fi ] 0 , 1 ≤ i ≤ n. In membrane 0, we subsequently choose each variable xi , 1 ≤ i ≤ n, and both values true and f alse are associated with it, in form of objects ti and fi , which are separated in two membranes with label 0. The division of membrane 0 is triggered by the objects ai , which are introduced by the ?rst rule from group G1 in odd steps; this is important in interleaving the use of these rules (hence the division of membrane 0) with the use of the rules of group G4, for dividing membranes placed above membrane 0. G3 [ ti → vi ] 0 , [ fi → vi ] 0 , 0 ≤ i < n. In membrane 0, we subsequently look for the clauses satis?ed by the truth assignments of each variable xi , 1 ≤ i ≤ n. After 2n + m steps, if there is at least one membrane with label 0 which contains all the symbols c1 , · · · , cm , this means that the truth assignment from that membrane satis?es all clauses, hence it satis?es formula β. Otherwise (if in no membrane with label 0 we get all objects c1 , c2 , . . . , cm ), the formula β is not satis?able. 28

G4 [ [ ] i [ ] i ] i+1 → [ [ ] i ] i+1 [ [ ] i ] i+1 , 0 ≤ i < m. These are division rules for membranes with label 0, 1, · · · , m, to be used for the central membrane 0 in steps which alternate with the use of the ?rst rule of type G1. The division of a membrane with label 1 is then propagated from lower levels to upper levels of the membrane structure and the membranes are continuously divided until also membrane with label m has been divided. In the following cycle of the division process, the same holds, resulting in the structure as shown in Fig. 1 after 2n + m steps. G5 [ d2n+m ] 0 → c0 . After 2n + m steps, each copy of membrane with label 0 is dissolved and the contents is released into the surrounding membrane, which is labeled with 1. Checking phase C1 [ ci ] i → ci , 1 ≤ i ≤ m, A membrane with label j, 1 ≤ j ≤ m, is dissolved if and only if cj appears in it (i.e., clause Cj is satis?ed by the current truth assignment); if this is the case, the truth assignment associated with the membrane is released in the surrounding membrane. Otherwise, the truth assignment remains blocked in membrane j and never used at the next steps by the membranes placed above. C2 [ c0 ] m+1 → c0 . The fact the object c0 appears in the membrane with the label m + 1 means that there is a truth assignment which satis?es the formula β. In this case, the membrane with label m + 1 is dissolved and the contents are released into the membrane with label m + 2. Otherwise, the formula is not satis?able, and the membrane with label m + 1 will not dissolve. C3 [ di → di+1 ] m+1 , 0 ≤ i ≤ 2n + 2m + 1. At the same time as the membrane with label m + 1 is dissolved (at step 2n + 2m + 1), the object d2n+2m+1 evolves to d2n+2m+2 , and then released to the membrane with label m + 2. Output phase O1 [ d2n+2m+2 ] m+2 → yes. O2 [ a] m+3 → [ ] m+3 a, a ∈ {yes, no}. In the next two steps, the object yes is produced, and then send out to the environment. O3 [ d2n+2m+2 ] m+1 → no. O4 [ no] m+2 → no. 29

If the formula is not satis?able, then the object d2n+2m+1 remains in the membrane with label m + 1, which produces the object no, ejecting it into the membrane with label m + 2, then into the membrane with label m + 3, ?nally into the environment. Therefore, in 2n + 2m + 3 the system halts and sends into the environment one of the objects yes, no, indicating whether or not the formula β is satis?able. It is easy to see that the system Π can be constructed in a polynomial time starting from β and this concludes the proof. Remark 3. Rules of type (c0 ) are only needed to output the result in the environment, so this type can be omitted if we consider internal output: exactly one of objects yes and no will be introduced in the skin membrane in the last step of the computation.

m+3 m+2 m+1

s s

m

s 7e ? 7? e 7 ? e 7m s es ? 7 s e m

···

m-1 s m-1 s . . . 1 0 . . .

s m-1

. . . ···

s 1 s s 0 s 2n

s s

1 0

Fig. 1. The membrane structure of the system Π after 2n + m steps.

6

Final Remarks

With the goal of removing the polarization from P systems with active membranes, we have investigated the possibility to allow instead to change the labels of membranes, and we were successful in the case of rules for sending objects out of a membrane (of type (c)) and in the case of rules for dividing membranes (of type (e)) – losing however the determinism. The case of using rules of type (b) (introducing objects into membranes) for changing the labels has remained open in what concerns the simulation results – as well as the possibility to solve SAT in polynomial time – but not in what concerns the universality. 30

The use of non-polarized membranes suggests further possibilities in what concerns the application of rules. For instance, as already mentioned in Section 4.5, one of the reasons to use the rules of types (b), (c) in a sequential way was the polarization change (using several rules at the same time could lead to polarization con?icts). The same reason prevents using rules of types (b0 ), (c0 ) in a parallel manner. When no polarizations are present and no label is changed, these di?culties do not appear, hence we can use also rules of types (b0 ), (c0 ) in parallel: all objects which can enter or exit a membrane have to do it at the same time, in the maximally parallel manner. On the other hand, we can allow also rules of type (a) to change the polarization or the label of the membrane – and then such a rule should be applied in a sequential manner, not to lead to label con?icts. We write such a rule in the e e form [ a] h1 → [ v] h2 , or [ a] h1 → [ v] h2 . In total, we get three criteria to classify the rules: changing or not polarizations, changing or not labels of membranes, using the rules in parallel or sequentially. On the other hand, we have rules of ?ve forms (six, if we also consider rules for dividing non-elementary membranes), each one being of several possible types with respect to the previous classi?cation. A lot of classes of P systems are obtained by combining these possibilities, a small “jungle” which is worth exploring, looking for results of three types: simulation lemmas among di?erent classes of P systems, universality results (as a consequence of possible simulation lemmas or directly proven), e?ciency results. We hope to return to this topic in a forthcoming paper. Acknowledgements. The ?rst author was supported by grant 2001CAJALBURV4 from Rovira i Virgili University, and the second author by grant DGUSB2001-0092 from Spanish Ministry for Education, Culture, and Sport, National Natural Science Foundation of China (Grant No. 60103021), and Huazhong University of Science and Technology Foundation.

References

1. A. Alhazov, C. Mart? ?n-Vide, L. Pan, Solving a PSPACE-Complete Problem by P Systems with Restricted Active Membranes, Fundamenta Informaticae, to appear. 2. F. Bernardini, V. Manca, P Systems with Boundary Rules, Membrane Computing. Proc. WMC Curtea de Arge?, 2002 (Gh. P?un, G. Rozenberg, A. Salomaa, C. s a Zandron, eds.), LNCS 2597, Springer-Verlag, 2003, 107–118. a 3. J. Dassow, Gh. P?un, Regulated Rewriting in Formal Language Theory, SpringerVerlag, Berlin, 1989. 4. D. Hauschild, M. Jantzen, Petri Nets Algorithms in the Theory of Matrix Grammars, Acta Informatica, 31 (1994), 719–728. 5. M. Madhu, K. Krithivasan, Improved Results About the Universality of P Systems, Bulletin of the EATCS, 76 (February 2002), 162–168. 6. Ch.P. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994. 7. A. P?un, Gh. P?un, The Power of Communication: P Systems with Syma a port/Antiport, New Generation Computers, 20, 3 (2002), 295–306.

31

8. Gh. P?un, P Systems with Active Membranes: Attacking NP-Complete Problems, a Journal of Automata, Languages and Combinatorics, 6, 1 (2001), 75–90. 9. Gh. P?un, Computing with Membranes: An Introduction, Springer-Verlag, Berlin, a 2002. 10. M.J. P?rez Jim?nez, A. Romero Jim?nez, F. Sancho Caparrini, The Polynomial e e e Complexity Class with Active Membranes, submitted, 2003. e e e ?a 11. M.J. P?rez-Jim?nez, A. Romero-Jim?nez, F. Sancho-Caparrini, Teor? de la Complejidad en Modelos de Computati?n Celular con Membranas, Editorial Kronos, o Sevilla, 2002. 12. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages (3 volumes). Springer, Berlin, 1997. 13. A. Salomaa: Formal Languages. Academic Press, New York, 1973. 14. P. Sos? Solving a PSPACE-Complete Problem by P Systems with Active Mem?k, branes, Proceedings of the Brainstorming Week on Membrane Computing (M. Cavaliere, C. Mart? ?n-Vide, and Gh. P?un, eds.), Report GRLMC 26/03, 2003, 305–312. a

32

赞助商链接

更多相关文章：
更多相关标签：