On the Power of Deterministic EC P Systems

On the Power of Deterministic EC P Systems Artiom ALHAZOV Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T´arraco 1, 43005 Tarragona, Spain E-mail: [email protected] Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] Abstract. It is commonly believed that a significant part of the computational power of membrane systems comes from their inherent non-determinism. Recently, R. Freund and Gh. P˘aun have considered deterministic P systems, and formulated the general question whether the computing (generative) capacity of non-deterministic P systems is strictly larger than the (recognizing) capacity of their deterministic counterpart. In this paper, we study the computational power of deterministic P systems in the evolution–communication framework. It is known that, in the generative case, two membranes are enough for universality. For the deterministic systems, we obtain the universality with three membranes, leaving the original problem open. 1 Introduction We assume the reader familiar with membrane computing (see http://psystems. disco.unimib.it for the bibliography). The evolution–communication P systems, introduced by M. Cavaliere in [2], are the P systems with two types of rules: simple (i.e., without targets) rewriting rules, and communication (i.e., symport/antiport rules). Agenerative P system starts from a fixed configuration, and (possibly) halts with a resulting number of objects (or multiset, or a sequence) in a specified region. A recognizing P system starts from a fixed configuration plus the input number (or multiset), and the input is accepted if and only if the computation halts. The purpose of this paper is to prove universality of deterministic recognizing evolution–communication (in short, EC) P systems. In the non-deterministic generative case, EC P systems are known to be universal even when using only two membranes (and symport/antiport rules of a rather small weight). At the price of using one further membrane, we show that the universality holds true also in the deterministic recognizing case; the symport/antiport rules used in the proof are still of a small weight. We do not know whether our results can be improved in the number of membranes. 11 2 Definitions A P system is deterministic if for every reachable non-halting configuration the next configuration is unique. In what follows, we consider P systems which accept numbers: to accept a number N, the system starts with the initial configuration, to which Ncopies of a specified object a are added in a specified region. The number is accepted if and only if the computation halts. The set of numbers accepted by a system Π is denoted by N(Π). The system being deterministic, there is only one computation (either halting, or non-halting) possible for every input. Let the P system have mmembranes and the set Oof objects. In this paper, the evolution–communication systems are considered, so the rules (applied in the maximallyparallel manner) are of the following forms: 1. a→x, associated to region i, 1 ≤i≤m, where a∈O,w∈O∗, 2. (x, out), (y, in), (x, out;y, in), associated to membrane i, where 1 ≤i≤m,x, y ∈O+. Thus, the recognizing P system can be denoted as Π = (O, µ, w1,···, wm, R1,· · · , Rm, R0 1,· · · , R0 m, i0), where µis the membrane structure, wiis the starting multiset of objects in region i,Ri is the set of rules of the first form (evolution), R0 iis the set of rules of the second form (communication), and i0is the input region. By NOPm(ncoo, symp, antiq) we denote the family of sets N(Π) generated by EC P systems with at most mmembranes, using non-cooperative evolution rules, symport rules of weight at most p, and antiport rules of weight at most q. When dealing with recognizing (accepting) systems, we add the subscript ato the front N, while, moreover, a Dis added in the case of using only deterministic systems. As usual, NRE is the family of Turing computable sets of numbers. 3 The Power It is known from [1] and [4] that NOP2(ncoo, sym1, ant1) = NOP2(ncoo, sym2) = NRE. We now present the deterministic counterparts of these results, using 3 membranes. Theorem 3.1 DNaOP3(ncoo, sym1, ant1) = NRE. Proof. Given a set M∈NRE, consider a deterministic register machine G= (m, einit, ehalt, P ) with mregisters, initial label einit, halting label ehalt, instruction set P, and set Lab(P) of labels, accepting M. We construct the following P system (object airepresents the the value of the ith register of G) Π=(O, µ = [1[2[3]3]2]1, w1=λ, w2=einit, w3=λ, R1, R2, R3, R0 1=∅, R0 2, R0 3,2), O={e, e0, e1, e2, e3, e4, e5, e6|e∈Lab(P)} ∪ {ar|1≤r≤m} ∪ {s1, s2, s3, q, z}, 12 R1={s1→s2} ∪ {ar→λ|1≤r≤m} ∪ {e3→e4|(e:dec(r), f, g)∈P}, R2={s3→λ} ∪ {e→arf|(e:inc(r), f)∈P} ∪ {e→s1e0, e0→e1, e1→e2, e2→e3, e4→e5q, e5→e6, e6→z |(e:dec(r), f, g)∈P}, R3={s2→s3, q →λ}∪{e3→f|(e:dec(r), f, g)∈P}, R0 2={(s1, out),(ar, out;s2, in)} ∪ {(e3, out;s2, in),(e4, in)|(e:dec(r), f, g)∈P}, R0 3={(s2, in),(s3, out;q, in)}∪{(f, out)|(e:dec(r), f, g)∈P} ∪ {(s3, out;e3, in)|(e:dec(r), f, g)∈P}. The P system above recognizes a number Nif and only if the computation, starting with aN 1(the input register of Gis the first one) placed in region 2, halts. Below are the simulations of individual instructions. Instruction (e:inc(r), f) is simulated in the following way: [1[2ew[3]3]2]1⇒[1[2arfw[3]3]2]1. The object e(corresponding to the instruction label) simply evolves into arf, thus changing instruction label from eto fand adding one to the counter r. Instruction (e:dec(r), f, g) (in case register ris non-zero) is simulated as follows: [1[2earw[3]3]2]1⇒[1[2s1e0arw[3]3]2]1⇒[1s1[2e1arw[3]3]2]1 ⇒[1s2[2e2arw[3]3]2]1⇒[1ar[2s2e3w[3]3]2]1⇒[1[2e3w[3s2]3]2]1 ⇒[1[2e3w[3s3]3]2]1⇒[1[2s3w[3e3]3]2]1⇒[1[2w[3f]3]2]1⇒[1[2fw[3]3]2]1. The object e(corresponding to the instruction label) evolves into e0(changing in 3 steps into e3) and s1, which goes in region 1, then changes into s2, and then returns in region 2 in exchange for ar(which is then erased). Then, s2travels into region 3, changes to s3 and returns to region 2 (where it is then erased) in exchange for e3. Finally, e3, being in region 3, changes into fand return in region 2, finishing the simulation of the instruction. Instruction (e:dec(r), f, g) (in case register ris zero) is simulated as follows: [1[2ew[3]3]2]1⇒[1[2s1e0rw[3]3]2]1⇒[1s1[2e1w[3]3]2]1 ⇒[1s2[2e2w[3]3]2]1⇒[1s2[2e3w[3]3]2]1⇒[1e3[2s2w[3]3]2]1 ⇒[1e4[2w[3s2]3]2]1⇒[1[2e4w[3s2]3]2]1⇒[1[2e5qw[3s2]3]2]1 ⇒[1[2e6ws2[3q]3]2]1⇒[1[2zw[3]3]2]1. (Note that |w|ar= 0.) Like in the previous case, the object eevolves into e0(changing in 3 steps into e3) and s1, which goes in region 1, and then changes into s2. Now there is no object arin region 2 to bring s2to region 2, so s2remains in region 3 until the next step, when it is exchanged with e3. Then s2travels to region 3 and changes into s3. Now, e3, being in region 1, changes into e4, returns to region 2, where it evolves into e5(changing it two steps into z) and q, which exchanges with s3and then both qand s3are erased. 2 In the next theorem, symport of weight two is used instead of antiport of weight one, leading to one more universality result. 13 Theorem 3.2 DNaOP3(ncoo, sym2) = NRE. Proof. Given a set M∈NRE, consider a deterministic register machine G= (m, einit, ehalt, P ) as above, accepting M. We construct the following P system: Π=(O, µ = [1[2[3]3]2]1, w1=λ, w2=einit, w3=λ, R1, R2, R3, R0 1=∅, R0 2, R0 3,2), O={e, e0, e1, e2, e3, e4, e5, e6|e∈Lab(P)} ∪ {ar|1≤r≤m} ∪ {s1, s2, s3, q, z}, R1={q→λ, s2→λ}∪{e0→e1|(e:dec(r), f, g)∈P} ∪ {ar→λ|1≤r≤m}, R2={s1→s2} ∪ {e→s1e0, e1→e2q, e2→e3, e3→f|(e:dec(r), f, g)∈P} ∪ {e→arf|(e:inc(r), f)∈P}, R3={s2→λ} ∪ {e0→z|(e:dec(r), f, g)∈P}, R0 2={(qs2, out)} ∪ {(e0ar, out),(e1, in)|(e:inc(r), f)∈P}, R0 3={(s2e0, in),(z, out)|(e:dec(r), f, g)∈P)}. The P system above recognizes a number Nif and only if the computation, starting with aN 1(the first register is the input one of G) placed in region 2, halts. Below is the simulation of the instructions of G. Instruction (e:inc(r), f) is simulated like in the previous theorem: [1[2ew[3]3]2]1⇒[1[2Rfw[3]3]2]1. Instruction (e:dec(r), f, g) is simulated in the following way: The object eevolves in e0(used to subtract) and s1(which changes into s2, the helper). [1[2earw[3]3]2]1⇒[1[2s1e0arw[3]3]2]1⇒[1e0ar[2s2w[3]3]2]1 ⇒[1e1[2s2w[3]3]2]1⇒[1[2e1s2w[3]3]2]1⇒[1[2e2qs2w[3]3]2]1 ⇒[1qs2[2e3w[3]3]2]1⇒[1[2fw[3]3]2]1. If aris present in region 2, then (one copy of) argoes to region 1 (where it is erased) together with e0, which changes into e1, returns to region 2, and then evolves into e2 (which changes into fin two steps) and q, which exists to region 1 together with s2, where both qand s2are erased. [1[2ew[3]3]2]1⇒[1[2s1e0w[3]3]2]1⇒[1[2s2e0w[3]3]2]1 ⇒[1[2w[3s2e0]3]2]1⇒[1[2w[3z]3]2]1⇒[1[2zw[3]3]2]1. (Note that |w|ar= 0.) If aris not present in region 2, then e0waits for s2, they both come to region 3, where s2is erased, while e0changes to zand returns to region 2, finishing the simulation of the instruction. 2 4 Conclusions This paper gives two three-membrane constructions for the universal deterministic evolution–communication P systems, one using symport of weight at most two, and the 14 other one using symport and antiport of weight one. These results are incomparable with the existing (nondeterministic) universality results with two membranes, as the proofs rely on having three regions where evolution rules take place. It is an open question whether the EC P systems with two membranes are universal in the deterministic way with symport of weight at most two, or with symport and antiport of weight one. Acknowledgements. The author acknowledges IST-2001-32008 project “Mol- CoNet”, as well as 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. References [1] A. Alhazov, Minimizing Evolution-Communication P Systems and EC P Automata, Brainstorming Week on Membrane Computing (M. Cavaliere, C. Mart´ın-Vide, Gh. P˘aun, eds.), Rovira i Virgili University, Technical Report 26/03, Tarragona, 2003, 23–31, and New Generation Computing, accepted for publication. [2] M. Cavaliere, Evolution-Communication P Systems, Membrane Computing. International Workshop, WMC-CdeA 2002, Curtea de Arge¸s (Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron, eds.), Springer-Verlag, LNCS 2597, Berlin, 2003, 134–145. [3] R. Freund, Gh. P˘aun, On Deterministic P Systems, submitted, 2003. [4] S.N. Krishna, A. P˘aun, Some Universality Results on Evolution-Communication P Systems, Brainstorming Week on Membrane Computing (M. Cavaliere, C. Mart´ın- Vide, Gh. P˘aun, eds.), Rovira i Virgili University, Technical Report 26/03, Tarragona, 2003, 207–215. [5] Gh. P˘aun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002. 15