On the Power of Deterministic EC P Systems

On he Powe o De e minis ic EC P Sys ems A iom ALHAZOV Resea ch G oup on Ma hema ical Linguis ics Ro i a i Vi gili Uni e si y Pl. Impe ial T´a aco 1, 43005 Ta agona, Spain E-mail: [email p o ec ed] Ins i u e o Ma hema ics and Compu e Science Academy o Sciences o Moldo a S . Academiei 5, Chi¸sin˘au, MD 2028, Moldo a E-mail: [email p o ec ed] Abs ac . I is commonly belie ed ha a signi ican pa o he compu a ional powe o memb ane sys ems comes om hei inhe en non-de e minism. Re- cen ly, R. F eund and Gh. P˘aun ha e conside ed de e minis ic P sys ems, and o mula ed he gene al ques ion whe he he compu ing (gene a i e) capaci y o non-de e minis ic P sys ems is s ic ly la ge han he ( ecognizing) capaci y o hei de e minis ic coun e pa . In his pape , we s udy he compu a ional powe o de e minis ic P sys ems in he e olu ion–communica ion amewo k. I is known ha , in he gene a- i e case, wo memb anes a e enough o uni e sali y. Fo he de e minis ic sys ems, we ob ain he uni e sali y wi h h ee memb anes, lea ing he o iginal p oblem open. 1 In oduc ion We assume he eade amilia wi h memb ane compu ing (see h p://psys ems. disco.unimib.i o he bibliog aphy). The e olu ion–communica ion P sys ems, in- oduced by M. Ca alie e in [2], a e he P sys ems wi h wo ypes o ules: simple (i.e., wi hou a ge s) ew i ing ules, and communica ion (i.e., sympo /an ipo ules). Agene a i e P sys em s a s om a ixed con igu a ion, and (possibly) hal s wi h a esul ing numbe o objec s (o mul ise , o a sequence) in a speci ied egion. A ecognizing P sys em s a s om a ixed con igu a ion plus he inpu numbe (o mul ise ), and he inpu is accep ed i and only i he compu a ion hal s. The pu pose o his pape is o p o e uni e sali y o de e minis ic ecognizing e olu ion–communica ion (in sho , EC) P sys ems. In he non-de e minis ic gene a- i e case, EC P sys ems a e known o be uni e sal e en when using only wo memb anes (and sympo /an ipo ules o a a he small weigh ). A he p ice o using one u he memb ane, we show ha he uni e sali y holds ue also in he de e minis ic ecognizing case; he sympo /an ipo ules used in he p oo a e s ill o a small weigh . We do no know whe he ou esul s can be imp o ed in he numbe o memb anes. 11 2 De ini ions A P sys em is de e minis ic i o e e y eachable non-hal ing con igu a ion he nex con- igu a ion is unique. In wha ollows, we conside P sys ems which accep numbe s: o accep a numbe N, he sys em s a s wi h he ini ial con igu a ion, o which Ncopies o a speci ied objec a a e added in a speci ied egion. The numbe is accep ed i and only i he compu a ion hal s. The se o numbe s accep ed by a sys em Π is deno ed by N(Π). The sys em being de e minis ic, he e is only one compu a ion (ei he hal ing, o non-hal ing) possible o e e y inpu . Le he P sys em ha e mmemb anes and he se Oo objec s. In his pape , he e olu ion–communica ion sys ems a e conside ed, so he ules (applied in he maximally- pa allel manne ) a e o he ollowing o ms: 1. a→x, associa ed o egion i, 1 ≤i≤m, whe e a∈O,w∈O∗, 2. (x, ou ), (y, in), (x, ou ;y, in), associa ed o memb ane i, whe e 1 ≤i≤m,x, y ∈O+. Thus, he ecognizing P sys em can be deno ed as Π = (O, µ, w1,···, wm, R1,· · · , Rm, R0 1,· · · , R0 m, i0), whe e µis he memb ane s uc u e, wiis he s a ing mul ise o objec s in egion i,Ri is he se o ules o he i s o m (e olu ion), R0 iis he se o ules o he second o m (communica ion), and i0is he inpu egion. By NOPm(ncoo, symp, an iq) we deno e he amily o se s N(Π) gene a ed by EC P sys ems wi h a mos mmemb anes, using non-coope a i e e olu ion ules, sympo ules o weigh a mos p, and an ipo ules o weigh a mos q. When dealing wi h ecognizing (accep ing) sys ems, we add he subsc ip a o he on N, while, mo eo e , a Dis added in he case o using only de e minis ic sys ems. As usual, NRE is he amily o Tu ing compu able se s o numbe s. 3 The Powe I is known om [1] and [4] ha NOP2(ncoo, sym1, an 1) = NOP2(ncoo, sym2) = NRE. We now p esen he de e minis ic coun e pa s o hese esul s, using 3 memb anes. Theo em 3.1 DNaOP3(ncoo, sym1, an 1) = NRE. P oo . Gi en a se M∈NRE, conside a de e minis ic egis e machine G= (m, eini , ehal , P ) wi h m egis e s, ini ial label eini , hal ing label ehal , ins uc ion se P, and se Lab(P) o labels, accep ing M. We cons uc he ollowing P sys em (objec ai ep esen s he he alue o he i h egis e o G) Π=(O, µ = [1[2[3]3]2]1, w1=λ, w2=eini , w3=λ, R1, R2, R3, R0 1=∅, R0 2, R0 3,2), O={e, e0, e1, e2, e3, e4, e5, e6|e∈Lab(P)} ∪ {a |1≤ ≤m} ∪ {s1, s2, s3, q, z}, 12 R1={s1→s2} ∪ {a →λ|1≤ ≤m} ∪ {e3→e4|(e:dec( ), , g)∈P}, R2={s3→λ} ∪ {e→a |(e:inc( ), )∈P} ∪ {e→s1e0, e0→e1, e1→e2, e2→e3, e4→e5q, e5→e6, e6→z |(e:dec( ), , g)∈P}, R3={s2→s3, q →λ}∪{e3→ |(e:dec( ), , g)∈P}, R0 2={(s1, ou ),(a , ou ;s2, in)} ∪ {(e3, ou ;s2, in),(e4, in)|(e:dec( ), , g)∈P}, R0 3={(s2, in),(s3, ou ;q, in)}∪{( , ou )|(e:dec( ), , g)∈P} ∪ {(s3, ou ;e3, in)|(e:dec( ), , g)∈P}. The P sys em abo e ecognizes a numbe Ni and only i he compu a ion, s a ing wi h aN 1( he inpu egis e o Gis he i s one) placed in egion 2, hal s. Below a e he simula ions o indi idual ins uc ions. Ins uc ion (e:inc( ), ) is simula ed in he ollowing way: [1[2ew[3]3]2]1⇒[1[2a w[3]3]2]1. The objec e(co esponding o he ins uc ion label) simply e ol es in o a , hus changing ins uc ion label om e o and adding one o he coun e . Ins uc ion (e:dec( ), , g) (in case egis e is non-ze o) is simula ed as ollows: [1[2ea w[3]3]2]1⇒[1[2s1e0a w[3]3]2]1⇒[1s1[2e1a w[3]3]2]1 ⇒[1s2[2e2a w[3]3]2]1⇒[1a [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[3 ]3]2]1⇒[1[2 w[3]3]2]1. The objec e(co esponding o he ins uc ion label) e ol es in o e0(changing in 3 s eps in o e3) and s1, which goes in egion 1, hen changes in o s2, and hen e u ns in egion 2 in exchange o a (which is hen e ased). Then, s2 a els in o egion 3, changes o s3 and e u ns o egion 2 (whe e i is hen e ased) in exchange o e3. Finally, e3, being in egion 3, changes in o and e u n in egion 2, inishing he simula ion o he ins uc ion. Ins uc ion (e:dec( ), , g) (in case egis e is ze o) is simula ed as ollows: [1[2ew[3]3]2]1⇒[1[2s1e0 w[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. (No e ha |w|a = 0.) Like in he p e ious case, he objec ee ol es in o e0(changing in 3 s eps in o e3) and s1, which goes in egion 1, and hen changes in o s2. Now he e is no objec a in egion 2 o b ing s2 o egion 2, so s2 emains in egion 3 un il he nex s ep, when i is exchanged wi h e3. Then s2 a els o egion 3 and changes in o s3. Now, e3, being in egion 1, changes in o e4, e u ns o egion 2, whe e i e ol es in o e5(changing i wo s eps in o z) and q, which exchanges wi h s3and hen bo h qand s3a e e ased. 2 In he nex heo em, sympo o weigh wo is used ins ead o an ipo o weigh one, leading o one mo e uni e sali y esul . 13 Theo em 3.2 DNaOP3(ncoo, sym2) = NRE. P oo . Gi en a se M∈NRE, conside a de e minis ic egis e machine G= (m, eini , ehal , P ) as abo e, accep ing M. We cons uc he ollowing P sys em: Π=(O, µ = [1[2[3]3]2]1, w1=λ, w2=eini , w3=λ, R1, R2, R3, R0 1=∅, R0 2, R0 3,2), O={e, e0, e1, e2, e3, e4, e5, e6|e∈Lab(P)} ∪ {a |1≤ ≤m} ∪ {s1, s2, s3, q, z}, R1={q→λ, s2→λ}∪{e0→e1|(e:dec( ), , g)∈P} ∪ {a →λ|1≤ ≤m}, R2={s1→s2} ∪ {e→s1e0, e1→e2q, e2→e3, e3→ |(e:dec( ), , g)∈P} ∪ {e→a |(e:inc( ), )∈P}, R3={s2→λ} ∪ {e0→z|(e:dec( ), , g)∈P}, R0 2={(qs2, ou )} ∪ {(e0a , ou ),(e1, in)|(e:inc( ), )∈P}, R0 3={(s2e0, in),(z, ou )|(e:dec( ), , g)∈P)}. The P sys em abo e ecognizes a numbe Ni and only i he compu a ion, s a ing wi h aN 1( he i s egis e is he inpu one o G) placed in egion 2, hal s. Below is he simula ion o he ins uc ions o G. Ins uc ion (e:inc( ), ) is simula ed like in he p e ious heo em: [1[2ew[3]3]2]1⇒[1[2R w[3]3]2]1. Ins uc ion (e:dec( ), , g) is simula ed in he ollowing way: The objec ee ol es in e0(used o sub ac ) and s1(which changes in o s2, he helpe ). [1[2ea w[3]3]2]1⇒[1[2s1e0a w[3]3]2]1⇒[1e0a [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[2 w[3]3]2]1. I a is p esen in egion 2, hen (one copy o ) a goes o egion 1 (whe e i is e ased) oge he wi h e0, which changes in o e1, e u ns o egion 2, and hen e ol es in o e2 (which changes in o in wo s eps) and q, which exis s o egion 1 oge he wi h s2, whe e bo h qand s2a e e ased. [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. (No e ha |w|a = 0.) I a is no p esen in egion 2, hen e0wai s o s2, hey bo h come o egion 3, whe e s2is e ased, while e0changes o zand e u ns o egion 2, inishing he simula ion o he ins uc ion. 2 4 Conclusions This pape gi es wo h ee-memb ane cons uc ions o he uni e sal de e minis ic e olu ion–communica ion P sys ems, one using sympo o weigh a mos wo, and he 14 o he one using sympo and an ipo o weigh one. These esul s a e incompa able wi h he exis ing (nonde e minis ic) uni e sali y esul s wi h wo memb anes, as he p oo s ely on ha ing h ee egions whe e e olu ion ules ake place. I is an open ques ion whe he he EC P sys ems wi h wo memb anes a e uni e sal in he de e minis ic way wi h sympo o weigh a mos wo, o wi h sympo and an ipo o weigh one. Acknowledgemen s. The au ho acknowledges IST-2001-32008 p ojec “Mol- CoNe ”, as well as he Moldo an Resea ch and De elopmen Associa ion (MRDA) and he U.S. Ci ilian Resea ch and De elopmen Founda ion (CRDF), Awa d No. MM2-3034 o p o iding a challenging and ui ul amewo k o coope a ion. Re e ences [1] A. Alhazo , Minimizing E olu ion-Communica ion P Sys ems and EC P Au oma a, B ains o ming Week on Memb ane Compu ing (M. Ca alie e, C. Ma ´ın-Vide, Gh. P˘aun, eds.), Ro i a i Vi gili Uni e si y, Technical Repo 26/03, Ta agona, 2003, 23–31, and New Gene a ion Compu ing, accep ed o publica ion. [2] M. Ca alie e, E olu ion-Communica ion P Sys ems, Memb ane Compu ing. In e na- ional Wo kshop, WMC-CdeA 2002, Cu ea de A ge¸s (Gh. P˘aun, G. Rozenbe g, A. Salomaa, C. Zand on, eds.), Sp inge -Ve lag, LNCS 2597, Be lin, 2003, 134–145. [3] R. F eund, Gh. P˘aun, On De e minis ic P Sys ems, submi ed, 2003. [4] S.N. K ishna, A. P˘aun, Some Uni e sali y Resul s on E olu ion-Communica ion P Sys ems, B ains o ming Week on Memb ane Compu ing (M. Ca alie e, C. Ma ´ın- Vide, Gh. P˘aun, eds.), Ro i a i Vi gili Uni e si y, Technical Repo 26/03, Ta agona, 2003, 207–215. [5] Gh. P˘aun, Memb ane Compu ing. An In oduc ion, Sp inge -Ve lag, Be lin, 2002. 15