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