Further Remarks on P Systems with Active Membranes, Separation, Merging, and Release Rules

Further Remarks on P Systems with Active Membranes, Separation, Merging, and Release Rules Linqiang PAN1,3, Artiom ALHAZOV2,3, Tseren-Onolt ISHDORJ3 1Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, People’s Republic of China E-mail: [email protected] 2Institute of Mathematics and Computer Science Academy of Science of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] 3Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T´arraco 1, 43005 Tarragona, Spain E-mail: {lp@fll,artiome.alhazov@estudiants, tserenonolt.ishdorj@estudiants}.urv.es Abstract. The P systems are a class of distributed parallel computing devices of a biochemical type. In this note, we show that by using membrane separation to obtain exponential workspace, SAT problem can be solved in linear time in a uniform and confluent way by active P systems without polarizations. This improves some results already obtained by A. Alhazov, Ts. Ishdorj. A universality result related to membrane separation is also obtained. 1 Introduction The P systems are a class of distributed parallel computing devices of a biochemical type, introduced in [4], which can be seen as a general computing architecture where various types of objects can be processed by various operations. The approach 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 [4], [5]. Informally speaking, in P systems with active membranes without polarizations one uses six types of rules: (a0) multiset rewriting rules, (b0) rules for introducing objects into membranes, (c0) rules for sending objects out of membranes, (d0) rules for dissolving membranes, (e0) rules for dividing elementary membranes, and (f0) rules for dividing non-elementary membranes, see [2]. In these rules, a single object participates during the 316 process. A few more types of rules are introduced in [1]: (g0) membrane merging rules, (h0) membrane separation rules, (i0) membrane release rules in P systems with active membranes without polarizations. A common feature of those rules is the use of multisets of objects during the computation process. By using membrane separation to obtain an exponential working space in a linear time, it is shown in [1] that SAT problem can be solved in linear time in a semi-uniform and confluent way by some particular combinations of types of rules in P systems with active membranes. In this note, the results are improved in the uniform way. A result about universality is also obtained. 2 P Systems with Active Membranes and New Membrane Operations We assume the reader to be familiar with basic elements of membrane computing, for instance, from [5] (details and recent results from membrane computing can be found at the web address http://psystems.disco.unimib.it). We only mention that RE denotes the family of recursively enumerable languages, and that for a family of languages FL, by PsF 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. The P systems with active membranes with some new operations (without polarization) of the form Π = (O, H, µ, w1, . . . , wm, R) were considered in [1], with the following components: where: 1. m≥1 is the initial degree of the system; 2. Ois the alphabet of objects; 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: (a0) [ a→v]h, for h∈H, a ∈O, v ∈O∗ (object evolution rules, associated with membranes and depending on the label, 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); (b0)a[ ]h→[b]h, for h∈H, a, b ∈O (communication rules; an object is introduced in the membrane during this process); (c0) [ a]h→[ ]hb, for h∈H, a, b ∈O (communication rules; an objects sent out of the membrane during this process); 317 (d0) [ a]h→b, for h∈H, 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); (e0) [ a]h→[b]h[c]h, for h∈H, 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; the object specified in the rule is replaced in the two new membranes by possibly new objects); (g0) [ ]h[ ]h→[ ]h, for h∈H (merging rules for elementary membranes; in reaction of two membranes, they are merged into a single membrane; the objects of the former membranes are put together in the new membrane); (h0) [ O]h→[U]h[O−U]h, for h∈H, U ⊂O (separation rules for elementary membranes; the membrane is separated into two membranes with the same labels; the objects from Uare placed in the first membrane, those from U−Oare placed in the other membrane); (i0) [ [ O]h]h→[ ]hO, for h∈H (release rule; the objects in a membrane are released out of a membrane, surrounding it, while the first membrane disappears). The rules are applied non-deterministically, in the maximally parallel manner; among the rules of types (b0),···,(i0) at most one can be applied to each membrane at each step. In this way, we get transition from a configuration of the system to the next configuration. A sequence of transitions is a computation. A computation is halting if no other rules can be applied in its last configuration. Rules of types (a0), (b0), (c0), (d0), and (e0) were introduced in [2], and (g0), (h0), and (i0) introduced in [1], without polarizations of membranes, and without the capability of changing the label of membranes they involve. Following the notation in [2] and [5], we use the primed versions to indicate the fact that the labels of membranes can be changed. For example, the primed versions of merging and separation rules are of the following forms: (g0 0) [ ]h1[ ]h2→[ ]h3, for h1, h2, h3∈H. (h0 0) [ O]h1→[U]h2[O−U]h3, for h1, h2, h3∈H, U ⊂O. To understand the difference of uniform construction and semi-uniform construction of P systems, we recall some notions about solving decidability problems in the membrane computing framework. Given a decision question 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 Πnwill 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. In [5], the complexity classes related to P systems are defined in the semi-uniform way: P systems are constructed starting not from the size n, but from an instance X(n). For a clearer description of the difference between uniform and semi-uniform constructions, please refer to [6]. 318 3 Efficiency From [1] we know that P systems with rules of types (a0), (b0), (c0), and (h0 0) can solve SAT in linear time in a semi-uniform and confluent way. The following theorem improves this result in a uniform way. Theorem 3.1 A uniform family of P systems with rules of types (a0),(b0),(c0),(h0 0)can solve SAT in linear time in a 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 βof SAT (to which the size (m, n) is associated) is encoded as a multiset over V(hn, mi) = {xi,j,j,¯xi,j,j |1≤i≤m, 1≤j≤n}. The object xi,j,j represents the variable xjappearing in the clause Ciwithout negation, and object ¯xi,j,j represents the variable xjappearing in the clause Ciwith negation. Thus, the input multiset is w={xi,j,j |xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n} ∪ {¯xi,j,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, µ, w0, w1, ws, R), O(hn, mi) = {xi,t,j,¯xi,t,j,|1≤i≤m, 0≤t≤j, 1≤j≤n} ∪ {x0 i,t,j,¯x0 i,t,j,|1≤i≤m, 0≤t≤j−1,1≤j≤n} ∪ {ci,j |1≤i≤m, 1≤j≤n+ 1}∪{c0 i,j |1≤i≤m, 1≤j≤n} ∪ {di|0≤i≤n+m+ 7} ∪ {d0 i|1≤i≤n+ 1} ∪ {t, λ, yes,no}, µ= [ [ ]0[ ]1]s, ws=λ, w0=d0, w1=d0, H={s, 0,1,· · · , m + 2}, and the following rules (we also give explanations about the use of these rules): Generation phase: G1. [ O]1→[U]1[O−U]1, U={x0 i,t,j,¯x0 i,t,j |1≤i≤m, 0≤t≤j−1,1≤j≤n} ∪ {c0 i,j |1≤i≤m, 1≤j≤n} ∪ {d0 i|1≤i≤n+ 1}. 319 G2. [ xi,t,j →xi,t−1,jx0 i,t−1,j]1, [ ¯xi,t,j →¯xi,t−1,j ¯x0 i,j−1,j]1, [x0 i,t,j →xi,t−1,jx0 i,t−1,j]1, [ ¯x0 i,t,j →¯xi,t−1,j ¯x0 i,t−1,j]1, 1 ≤i≤m, 1 ≤t≤j, 1 ≤j≤n. G3. [ xi,0,j →ci,jc0 i,j]1, [ ¯xi,0,j →λ]1, [ ¯x0 i,0,j →ci,jc0 i,j]1, [x0 i,0,j →λ]1, 1 ≤i≤m, 1 ≤j≤n. G4. [ ci,j →ci,j+1c0 i,j+1]1, [c0 i,j →ci,j+1c0 i,j+1]1, 1 ≤i≤m, 1 ≤j≤n−1. G5. [ ci,n →ci,n+1]1, [c0 i,n →ci,n+1]1, 1 ≤i≤m. G6. [ di→di+1d0 i+1]1, 0 ≤i≤n. [d0 i→di+1d0 i+1]1, 1 ≤i≤n. [dn+1 →dn+2]1. [d0 n+1 →dn+2]1. In n+ 1 steps, by rules of types G1–G4, 2nmembranes with label 1 are created, corresponding to the all possible 2ntruth assignments of the variables x1, x2, ..., xn. During this process, every object xi,j,j of the input evolves to xi,0,j and x0 i,0,j in jsteps. Then, they evolve to ci,j in membranes where true value was chosen for xj(recall that xi,j,j =true satisfies clause Ci) and are erased in membranes where false value was chosen for xj. In the next n−jsteps, ci,j evolves to ci,n or c0 i,n. It takes one more step ci,n and c0 i,n evolve to ci,n+1 by rules of type G5, which means the system is ready for checking phase. Similarly, ¯xi,j,j changes to ci,n+1 if xj=false and is erased if xj=true. Note that at step n+ 2, each membrane with label 1 has the object dn+2. Checking phase: C1. [ O]i→[U]i[O−U]i+1, U={ci,n+1},1≤i≤m. Starting with i= 1, in membranes with label i, objects ci,n+1 will be separated from the other objects, and the label of the membrane with objects from O− {ci,n+1}will become i+ 1. The membranes which do not contain the objects ci+1,n+1 will never evolve anymore. If all objects ci,n+1,1≤i≤m, are present in some membrane, then after m steps this membrane will evolve into a membrane with label m+1, containing object dn+2, by the rules of type C1. C2. [ dn+2]m+1 →[ ]m+1dn+2. C3. [ dn+2 →tt]s. If βhas solutions, then at step n+m+3, every membrane corresponding to a solution of βejects dn+2 in the skin region, then they will all be rewritten into tt. C4. t[ ]0→[t]0. 320 C5. t[ ]m+1 →[t]m+1. C6. [ O]0→[U0]m+1[O−U0]m+2, U0={t}. C7. [ di→di+1]0, 0 ≤i≤n+m+ 5. C8. [ dn+m+6 →dn+m+7]m+2. At step n+m+ 5, one copy of tenters the membrane with label 0, and (suppose β has ssolutions, 1 ≤s≤2n)scopies of tenter the smembranes with label m+ 1. At step n+m+ 6, s−1 copies of tenter the membranes with label m+ 1, or s−2 copies of t enter the s−2 membranes with label m+ 1, and 1 copy of tenters the membrane with label 0. Using rule C6, membrane with label 0 is separated into two membranes, which contain object tand object dn+m+6 or dn+m+7 respectively. If βhas no solution, then no object enters membrane labeled 0 and rule C6 is not applied. Output phase: O1. [ t→λ]m+1. O2. [ dn+m+7]0→[ ]0no. O3. [ dn+m+7]m+2 →[ ]m+2yes. O4. [ no]s→[ ]sno. O5. [ yes]s→[ ]syes. If βhas solutions, then at step n+m+ 8, object dn+m+7 in the membrane with label m+ 2 ejects yes into skin and then into the environment. If βhas no solution, then after n+m+ 8 steps object dn+m+7 ejects object no into skin and then into the environment. From the previous explanation of the use of rules, one can easily see how the P system designed in the above proof works, and it halts at step n+m+ 9. It is easy to prove that the designed P system is uniform. If βhas at least two solutions, then the behavior of this system is not deterministic: at step n+m+ 6 either one of the rules of types C4 and C6 can be applied to the membrane with label 0 (applying C4 in step 2n+ 2m+ 6 results in one extra copy of tin membrane with label 0 and one copy of tmissing in some membrane with label m+ 1). However, the system is confluent: in either case mentioned above, after three further steps, the system produces the output yes and halts in the same configuration (in the membranes with label m+ 1, the objects tare erased). 2 The following two theorems improve the corresponding theorems in [1], which are not difficult to be proved by using the generation phase in the proof of Theorem 3.1 and the proofs in Theorem 2 and 3 in [1]. So, here we omit the proofs. Theorem 3.2 A uniform family of P systems with rules of types (a0),(c0),(g0),(h0 0)can solve SAT in linear time in a confluent way. Theorem 3.3 A uniform family of P systems with rules of types (a0),(g0),(h0 0),(i0)can solve SAT in linear time in a confluent way. 321 4 Universality Because the notion of a matrix grammar will be used below, we introduce it here in its general form. Amatrix grammar with appearance checking is a construct G= (N, T, S, M, F ), where N, T are disjoint alphabets, S∈N,Mis a finite 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 Fis a set of occurrences of rules in M(Nis the nonterminal alphabet, Tis the terminal alphabet, Sis the axiom, while the elements of Mare called matrices). For w, z ∈(N∪T)∗we write w=⇒zif there is a matrix (A1→x1, . . . , An→xn) in Mand the strings wi∈(N∪T)∗,1≤i≤n+ 1, such that w=w1, z =wn+1,and, for all 1≤i≤n, either wi=w0 iAiw00 i, wi+1 =w0 ixiw00 i, for some w0 i, w00 i∈(N∪T)∗, or wi=wi+1, Aidoes not appear in wi, and the rule Ai→xiappears in F. (The rules of a matrix are applied in order, possibly skipping the rules in Fif they cannot be applied – therefore we say that these rules are applied in the appearance checking mode.) The language generated by Gis defined by L(G) = {w∈T∗|S=⇒∗w}.The family of languages of this form is denoted by MATac. It is known that MATac =RE. 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 Mare in one of the following forms: 1. (S→XA),with X∈N1, A ∈N2, 2. (X→Y, A →x),with X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x| ≤ 2, 3. (X→Y, A →#),with X, Y ∈N1, A ∈N2, 4. (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→XinitAinit), in order to fix the symbols X, A present in it), and Fconsists 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. Details can be found in [3]. The following theorem shows that by using membrane separation rule to change the labels of the membranes, the universality can be reached. Here Ps(Π) denotes the set of vectors of natural numbers describing the multiplicity of objects expelled into the environment by the various halting computations in system Π; by PsOP (a0, c0, h0 0) we denote the family of sets Ps(Π) computed by P systems using the types of rules a0,c0, and h0 0. Theorem 4.1 PsOP (a0, c0, h0 0) = PsRE. 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 above. Assume that all matrices of forms 2, 3, and 4 are injectively labeled with elements of a set B(without loss of generality, suppose 0 6∈ B), B=B1∪B2, B1for the matrices of forms 2 and 4, and B2for the matrices of form 3. Replace the rule X→λfrom matrices of type 4 by X→f, where fis a new symbol. 322 We construct the P system of degree 2 Π = (O, H, [ [ ]Xinit ]1, w1=λ, wXinit =c0Ainit, R), O=T∪N2∪ {Am|A∈N2, m ∈B1} ∪ {dm, d0 m|m∈B}∪{cm|m∈B2}∪{c0,#, λ}, H=N1∪ {Xm|X∈N1, m ∈B}∪{0,1, f}, and the set Rcontaining 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},A∈N2 and x∈(N2∪T)∗,|x| ≤ 2, is done in two steps, using the next rules: 1. [ A→Amdm]X, [O]X→[U]0[O−U]Ym,U={dm}, [c0→cndn]X,n∈B2, 2. [ Am→xd0 m]Ym, [O]Ym→[U]0[O−U]Y,U={d0 m}, [cn→c0]Ym,n∈B2, [dn→λ]Ym,n∈B2. The first rule of the matrix is simulated by the change of the label of the inner membrane by separation rule (the “dummy” objects dm,d0 m, and membrane 0 play no further role), and the correctness of this operation is obvious (one cannot simulate one rule of the matrix without simulating the other rule). The simulation of a matrix m: (X→Y, A →#), with X, Y ∈N1and A∈N2, is done also in two steps, using the next rules: 3. [ c0→cmdm]X, [O]X→[U]0[O−U]Ym,U={dm}, [A→Andn]X,n∈B1, 4. [ cm→c0d0 m]Ym, [O]Ym→[U]0[O−U]Y,U={d0 m}, [An→#]Ym,n∈B1, [A→#]Ym, [dn→λ]Ym,n∈B1. While the membrane with label Xis separated, if any copy of Ais present, then it can remain the same at this step (i.e., not evolving) and in the next step evolve to the trap-object # (this is the case if Adoes not appear in the matrices of type 2 and 4), or it evolves to Andn, in the next step the object Anintroduces the trap-object # and the computation never stops. If no Ais present, then the objects cmevolve, returning the label of the membrane to Yand introducing the auxiliary object c0, for iterating the procedure. We also consider the following rules: 5. [ A→#]f, for all A∈N2, 6. [ # →#]h, for all h∈H, 323 7. [ a]f→[ ]fa, for all a∈T, 8. [ 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 (h0 0)are sufficient to reach universality for membrane systems with internal output. 5 Final Remark This note shows that using membrane separation to obtain exponential workspace in a linear time, SAT problem can be solved in linear time in a uniform and confluent way by active P systems with membrane separation rules. In general, it is still open whether any semi-uniform solution to a problem can be modified to a uniform solution. By a direct proof, the universality related to separation rule is reached. In [2] by using division to change the labels of the membranes, we also have PsOP (a0, c0, e0 0) = P sRE. But it 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 DGU-SB2001-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 also the Moldovan Research and Development Association (MRDA) and the U.S. Civilian Research and Development Foundation (CRDF), Award No. MM2-3034 for providing a challenging and fruitful framework for cooperation. The third author acknowledges The State Training Fund of the Ministry of Science, Technology, Education and Culture of Mongolia. References [1] A. Alhazov, Ts. Ishdorj, Membrane Operations in P Systems with Active Membranes, in the present volume. [2] A. Alhazov, L. Pan, Gh. P˘aun, Trading Polarizations for Labels in P Systems with Active Membranes, submitted 2003. [3] J. Dassow, Gh. P˘aun, Regulated Rewriting in Formal Language Theory, SpringerVerlag, Berlin, 1989. [4] Gh. P˘aun, Computing with Membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143, and TUCS Research Report 208, 1998 (http://www.tucs.fi). [5] Gh. P˘aun, Membrane Computing: An Introduction, Springer, Heidelberg, 2002. [6] M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini, Complexity Classes in Models of Cellular Computing with Membranes, Natural Computing, 2(3) (2003), 265–285. 324