Size and Powe o Ex ended
Gemma ing P Pys ems
Daniela BESOZZI1, E zs´ebe CSUHAJ-VARJ ´
U2,
Gianca lo MAURI3, Claudio ZANDRON3
1Uni e si `a degli S udi di Milano
Dipa imen o di In o ma ica e Comunicazione
Via Comelico 39, 20135 Milano, I aly
E-mail: [email p o ec ed]
2Compu e and Au oma ion Resea ch Ins i u e
Hunga ian Academy o Sciences
Kende u. 13-17, H-1111 Budapes , Hunga y
E-mail: [email p o ec ed]
3Uni e si `a degli S udi di Milano-Bicocca
Dipa imen o di In o ma ica, Sis emis ica e Comunicazione
Via Bicocca degli A cimboldi 8, 20136 Milano, I aly
E-mail: {mau i,zand on}@disco.unimib.i
Abs ac . In [2] P sys ems wi h gemma ion o mobile memb anes we e ex-
amined. I was shown ha (ex ended) sys ems wi h eigh memb anes a e as
powe ul as he Tu ing machines. Mo eo e , i was also p o ed ha ex ended
gemma ing P sys ems wi h only p e-dynamical ules a e s ill compu a ionally
comple e: in his case nine memb anes a e needed o ob ain his compu a ional
powe . In his pape we imp o e he abo e esul s conce ning he size bound
o ex ended gemma ing P sys ems, namely we p o e ha hese sys ems wi h
a mos i e memb anes (wi h me a-p io i y ela ions and wi hou (in/ou )
communica ion ules) o m a class o uni e sal compu ing de ices, while in
he case o ex ended sys ems wi h only p e-dynamical ules six memb anes a e
enough o de e mine any ecu si ely enume able language.
1 In oduc ion
P sys ems wi h gemma ion o mobile memb anes we e in oduced in [3], de ining a new
kind o communica ion be ween memb anes which is inspi ed by ce ain biological p o-
cesses in li ing cells. The biological backg ound o he new model can be b ie ly sum-
ma ized as ollows: he cellula memb anes a e selec i ely pe meable o small subs ances
as, o example, wa e and gases, bu no o bigge subs ances as p o eins. These bigge
subs ances a e communica ed among he cells by means o esicles, encased on hei cy-
osolic ace by a speci ic p o ein which causes hei budding om he memb ane. When
he esicle uses wi h i s a ge memb ane, hen he ca ied p o eins a e in oduced inside
i , whe e hey can unde go di e en chemical eac ions. The eade can easily obse e
92
ha his p ocess can be modelled by so-called mobile memb anes, ha is, we can conside
some objec s in he o iginal memb ane o be anspo ed by means o small memb anes
o a a ge memb ane and hen being used wi h i .
To simula e hese ea u es, [3] in oduced P sys ems wi h gemma ion o mobile mem-
b anes. These a e a ian s o P sys ems wi h simple memb ane s uc u es, whe e he skin
memb ane con ains only elemen a y memb anes wi h s ing objec s which co espond o
p o eins o any o he s uc u ed bigge subs ances. These s ings e ol e acco ding o op-
e a ions wi h biochemical mo i a ions, namely mu a ion, eplica ion and spli ing. The
mu a ion in his case co esponds o he applica ion o a con ex - ee ule. Any memb ane
is p o ided wi h a se o classical e olu ion ules and a se o so-called p e-dynamical ules,
which a e ules de ining he gemma ion o he mobile memb anes. The e is a me a-p io i y
ela ion de ined be ween he se o classical e olu ion ules and he se o p e-dynamical
ules which is needed o simula e he comple ion o he ma u a ion pa h o an objec . A
p e-dynamical ule is a pa icula a ian o an e olu ion ule which also indica es he
memb ane whe e he s ing mus be communica ed. A e a p e-dynamical ule is used,
he modi ied s ing objec (s) is (a e) anspo ed in o he a ge memb ane, and om hen
i ( hey) will e ol e acco ding o he ules o his memb ane. This p ocedu e co esponds
o he gemma ion and he usion o he mobile memb ane. In pa icula , he ou pu o he
sys em is due o he usion o a mobile memb ane wi h he skin memb ane: his p ocess
causes he elease o he objec s ou side he sys em and simula es he biological p ocess
o exocy osis.
In [3, 2] P sys ems wi h gemma ion o mobile memb anes we e examined. I was
shown ha hese sys ems a e as powe ul as he Tu ing machines, in he case o ex ended
sys ems e en wi h eigh memb anes [2]. Mo eo e , i has also been p o ed ha ex ended
gemma ing P sys ems wi h only p e-dynamical ules a e s ill compu a ionally comple e: in
his case nine memb anes a e needed o ob ain his compu a ional powe [2]. Fo de ailed
in o ma ion on P sys ems wi h gemma ion o mobile memb anes consul also [1].
In his pape we imp o e he abo e esul s conce ning he size bound o ex ended
gemma ing P sys ems, namely we p o e ha hese sys ems consis ing o i e memb anes
(wi h me a-p io i y ela ions and wi hou (in/ou )- ules) o m a class o compu a ionally
comple e de ices, and o ex ended sys ems wi h only p e-dynamical ules six memb anes
a e enough o each he powe o he Tu ing machines.
2 Basic De ini ions
We assume ha he eade is amilia wi h o mal language heo y; o de ails and mo e
in o ma ion we e e o [5]. Th oughou he pape we use s anda d no ions and no a ions:
we deno e by V∗ he se o all wo ds o e an alphabe V, including he emp y wo d, λ. The
class o ecu si ely enume able languages is deno ed by RE; his is he class o languages
accep ed by he Tu ing machines o gene a ed by he class o ph ase-s uc u e o 0- ype
g amma s.
In his pape we shall use he no ion o a Ge e no mal o m o he ph ase-s uc u e
g amma s (see [5]). Acco ding o his esul , o any ecu si ely enume able language o e
an alphabe T he e exis s a gene a ing ph ase-s uc u e g amma G= (N, T, P, S),whe e
N={S, A, B, C},is he se o non e minals, Tis he se o e minals, Sis he s a symbol
o G, and he ules in P a e o he o ms S→uS , S →x, wi h u, , x ∈(T∪{A, B, C}∗),
and ABC →λ.
93
In he ollowing we ecall he de ini ion o ex ended P sys ems wi h gemma ion o
mobile memb anes om [2]. Fo de ailed in o ma ion abou P sys ems o memb ane
sys ems consul [4].
A memb ane s uc u e µis a cons uc ion consis ing o se e al memb anes hie a chi-
cally embedded in a unique memb ane, called he skin memb ane. A memb ane s uc u e
can also be iden i ied wi h a s ing o co ec ly ma ching squa e pa en heses, placed in a
unique pai o ma ching pa en heses. Each pai o ma ching pa en heses co esponds o a
memb ane.
By [2], gemma ing P sys ems use only memb ane s uc u es o dep h 2, ha is µ=
[0[1]1[2]2. . . [n−1]n−1[n]n]0. The skin memb ane will be always labelled wi h he numbe 0,
while he inne memb anes will be labelled wi h he numbe s 1, . . . , n.
P sys ems wi h gemma ion o mobile memb anes wo k wi h s ing-objec s whe e he
e olu ion ules a e able o mul iply he numbe o he s ings. The e o e, a mul ise o
ini e suppo is associa ed wi h e e y egion o he memb ane s uc u e. This mul ise is
a map ha associa es a mul iplici y o e e y s ing p esen in he egion, ha is we de ine
Mi:V+→Nwhe e Mi={(x1, Mi(x1)), . . . , (xp, Mi(xp))}, o some xk∈V+such ha
M(xk)>0, o all k= 1, . . . , p, i = 0,1, . . . , n.
Gemma ing P sys ems a e de ined wi h h ee ypes o ules wi h biochemical inspi a-
ion: mu a ion, eplica ion, and spli ing o a s ing. In his pape we use only mu a ion
ules.
A mu a ion ule is a con ex ee ule m:a→u, whe e a∈Vand u∈V∗. Fo s ings
w1, w2∈V+we w i e w1=⇒ mw2i w1=x1ax2and w2=x1ux2, o some x1,x2∈V∗.
When hese ope a ions a e applied o s ings in he memb ane sys ems, a ge indica-
ions a e added o he ules, de e mining he egions whe e he ob ained s ings will be
communica ed a he nex s ep.
Wi h each egion i= 0,1, . . . , n we associa e wo dis inc se s o ules:
•A se Cio classical e olu ion ules, ha is a se o mu a ion ules o he o m a→α,
whe e a∈Vand α= (u, a ),wi h u∈V∗,and a ∈ {he e, ou } o i= 1, . . . , n,
a ∈ {he e, ou }∪{in1, . . . , inn} o i= 0.
•A se Dio p e-dynamical e olu ion ules, ha is a se o mu a ion ules o he o m
a→(u, he e), wi h a∈V, such ha gi en a s ing w1=x1a(o w1=ax2) we ob ain
w2=x1u(w2=ux2, espec i ely), whe e u∈V∗·{@j}(u∈ {@j}·V∗, espec i ely)
and x1, x2∈V∗. Le e @jis a special symbol no in Vand j∈ {0,1, . . . , n}, j 6=i.
No ice ha a p e-dynamical ule can in oduce he special symbol @jonly a he ends
o he s ing. We will always conside he se D0as an emp y se , ha is no p e-dynamical
ule will e e be de ined inside he skin memb ane.
When a symbol @jappea s in some s ing wp esen in a memb ane i, o j6=i, hen
inside he P sys em wo sequen ial and dynamical communica ion p ocesses ake place. We
say ha a mobile memb ane, which we w i e as a couple o well-ma ching ound b acke s
(i,j)i,j ca ies he s ing w om he o igina ing memb ane i o he a ge memb ane j.
The communica ion s eps a e de ined by means o he ollowing ules.
•The gemma ion o a mobile memb ane is de ined as ollows:
[0. . . [i. . . , w@j, . . .]i. . .]0→[0. . . [i. . .]i(i,j w)i,j . . .]0
o some i∈ {1, . . . , n}, j ∈ {0,1, . . . , n}, j 6=i, w ∈V+.
Du ing his i s phase o he s ep he symbol @jis emo ed, i s subsc ip becomes
94
he second label o he mobile memb ane, hen s ing wlea es memb ane iand en e s
he c ea ed mobile memb ane. I he e a e se e al s ings o he o m w1@j, . . . , wk@j
inside memb ane i, all o hem wi h he same a ge memb ane j, hen a single
common mobile memb ane will be budded o om memb ane i:
[0. . . [i. . . , w1@j, . . . , wk@j, . . .]i. . .]0→
[0. . . [i. . .]i(i,jw1, . . . , wk)i,j . . .]0.
I inside memb ane i he e a e s ings o he o m w1@j1, . . . , wh1@j1, wh1+1@j2, . . . ,
wh2@j2, . . . , whk−1+1@jk, . . . , whk@jk(hk≥k) such ha j1, . . . , jka e pai wise di -
e en , hen kdi e en mobile memb anes will be gemma ed, each one con aining
he s ings di ec ed o he speci ied memb ane:
[0. . . [i. . . , w1@j1, . . . , wh1@j1, . . . , whk−1+1@jk, . . . , whk@jk, . . .]i. . .]0→
[0. . . [i. . .]i(i,j1w1, . . . , wh1)i,j1. . . (i,jkwhk−1+1, . . . , whk)i,jk. . .]0.
The case when a memb ane i, o some i∈ {1, . . . , n}, con ains one o mo e s ings
o he o m @jw, o some j∈ {0,1, . . . , n}can be analogously handled. Ob iously,
he same holds when a memb ane icon ains some s ings o bo h o ms.
•The usion o he mobile memb ane is de ined in he ollowing way:
[0. . . (i,jw)i,j[j. . .]j. . .]0→[0. . . [j. . . , w, . . .]j. . .]0,
o some i∈ {1, . . . , n}, j ∈ {1, . . . , n}, j 6=i, w ∈V+.
Du ing his second phase o he communica ion s ep he mobile memb ane becomes
a pa o he a ge memb ane, lea ing i s con en s inside i .
In pa icula , i j= 0 he mobile memb ane uses wi h he skin memb ane (in his
way we simula e he biological p ocess o exocy osis) and he objec s exi he sys em:
[0. . . (i,0w)i,0. . .]0→[0. . .]0w.
To keep he cons uc ion close o he unc ioning o eal cells, we de ine a me a-p io i y
ela ion be ween he whole se Ciand he whole se Di, o all i= 1, . . . , n, meaning ha
all applicable classical ules in Cimus be used be o e any applicable p e-dynamical ule
in Di. We ema k ha we do no de ine any p io i y ela ion be ween ules in he se Ci
nei he be ween ules in he se Di.
Now we gi e he o mal de ini ion o an ex ended P sys em Π wi h gemma ion o mobile
memb anes (o an ex ended gemma ing P sys em Π, in sho ) o deg ee n+ 1, n ≥0,as
ollows:
Π = (V, T, µ, M0, . . . , Mn,(C0,∅),(C1, D1), . . . , (Cn, Dn)),
whe e
–Vis an alphabe no con aining he symbols @0,@1, . . . , @n;
–T⊆Vis he ou pu ( e minal) alphabe ;
95
–µ= [0[1]1[2]2. . . [n−1]n−1[n]n]0is a memb ane s uc u e o dep h 2 and deg ee n+ 1;
–M0, . . . , Mna e mul ise s o ini e suppo o e V+;
– (Ci, Di), o all i= 0,1, . . . , n, a e a se o classical e olu ion ules and a se o p e-
dynamical e olu ion ules, espec i ely. The se Ci,i= 1, . . . , n, has a me a-p io i y
abo e Dias a as he applica ion o all o i s ules is conce ned. The se D0is
emp y.
An ex ended gemma ing P sys em wo ks as ollows: he egions a e p ocessed simul a-
neously, ha is, in e e y s ep, inside each egion, all he s ings which can be he subjec
o an e olu ion ule a e simul aneously ew i en. The ules o be applied can be nonde e -
minis ically chosen among all he applicable ules, in acco dance wi h he me a-p io i y
de ined o e he se o classical ules and he se o p e-dynamical ules. A each s ep
o a compu a ion a s ing can be ew i en by one ule only. The s ings esul ing a -
e he applica ion o a ule can emain inside he memb ane whe e hey a e placed, o
can be communica ed by mobile memb anes o by (in/ou ) communica ion o he egions
speci ied by he a ge indica ions.
The memb ane s uc u e a a gi en momen , oge he wi h all mul ise s o objec s
associa ed wi h he egions de ined by he memb ane s uc u e, o m he con igu a ion o
he sys em a ha momen .
Fo wo con igu a ions σ1= (µ, M0
0, . . . , M0
n) and σ2= (µ, M00
0, . . . , M00
n) o Π,we say
ha σ2is ob ained om σ1in one ansi ion by applying he ules in (Ci, Di), 0 ≤i≤n,
in acco dance wi h he me a-p io i y ela ion.
A sequence o ansi ions o ms a compu a ion. A compu a ion hal s when he e is no
ule which can be u he applied in he cu en con igu a ion. On he con a y, we say
ha a compu a ion is non-hal ing i he e is a leas one ule which can be applied o e e .
The ou pu o he P sys em Π (o he language o Π) is he se o s ings o e Texpelled
om he sys em du ing he compu a ion. The language gene a ed by Π is deno ed by L(Π).
Non-hal ing compu a ions p o ide no ou pu .
3 Size and Powe o Ex ended Gemma ing P Sys ems
In his sec ion we imp o e he esul o [2], namely, we show ha ex ended gemma ing P
sys ems consis ing o i e memb anes wi h me a-p io i y ela ions and wi hou he use o
(in/ou )- ules a e as powe ul as he Tu ing machines, and ex ended sys ems wi h only
p e-dynamical ules and wi hou any o he ea u e need six memb anes o his pu pose.
We deno e by EGemPm(MP i, α), o α∈ {(in/ou ), n(in/ou )}, he amily o lan-
guages gene a ed by ex ended gemma ing P sys ems o deg ee a mos m, o m≥1,
wi h ela ion o me a-p io i y and wi h he use (i α= (in/ou )) o wi hou he use (i
α=n(in/ou )) o communica ion ules o ype (in/ou ). I we use ∗ins ead o m, hen
we e e o he whole class o languages o ex ended gemma ing P sys ems wi h ela ion
o me a-p io i y and wi h he use (i α= (in/ou )) o wi hou he use (i α=n(in/ou ))
o communica ion ules o ype (in/ou ).
Fu he mo e, le us deno e by EGemPm(Dyn) he amily o languages gene a ed by
ex ended gemma ing P sys ems o deg ee m, o m≥1, wi h memb anes ha ing only
p e-dynamical ules. Analogously o he p e ious no a ions, EGemP∗(Dyn) deno es he
96

whole class o languages o ex ended gemma ing P sys ems wi h memb anes ha ing only
p e-dynamical ules.
We s a wi h he case o ex ended gemma ing P sys ems wi h only p e-dynamical
ules; he p oo o he o he s a emen can easily be ob ained by modi ying he p oo o
he ollowing heo em.
Theo em 1 EGemP6(Dyn) = EGemP∗(Dyn) = RE.
P oo . By [2] we should p o e only he inclusion RE ⊆EGemP6(Dyn). Fo his
pu pose, we modi y he p oo o he s a emen RE ⊆EGemP9(Dyn) in [2], whe e o any
ph ase-s uc u e g amma G= (N, T, S, P), gi en in he Ge e no mal o m, a simula ing
ex ended gemma ing P sys em wi h nine memb anes and wi h only p e-dynamical ules is
cons uc ed. The basic idea o his p oo is he so-called “ o a ion-and-simula ion”, which
is a echnique widely used in o mal language heo e ic models o molecula compu ing.
Acco ding o his me hod, o simula e he applica ion o a p oduc ion o a symbol A
occu ing somewhe e in he middle o he s ing, we mo e (we “ o a e”) one symbol s ep
by s ep om he igh end o he le end o he s ing, un il he symbol Aappea s on
he igh end. Then we apply he p oduc ion o A. To gua an ee he co ec simula ion
o a de i a ion in he g amma , a special symbol $ is in oduced o ma king he posi ion
whe e he o iginal (un o a ed) s ing begins. Since p e-dynamical ules can be applied
only a he igh end o a he le end o he s ing, his echnique is well applicable.
Le L⊆T∗be a ecu si ely enume able language gene a ed by a ph ase-s uc u e
g amma G= (N, T, S, P) gi en in he Ge e no mal o m. Le N0= (N {S}), and le
us deno e he elemen s in (N0∪T) by E1, . . . , En, n ≥1.Fu he mo e, le $, X, Y 6∈ (N∪T)
be auxilia y symbols. Symbol $, also deno ed by En+1, is used o ma king he beginning
o he s ing.
We cons uc he simula ing ex ended gemma ing P sys em o deg ee 6 as ollows. Le
Π = (V, T, µ, M0, . . . , M5,∅, D1, . . . , D5)
wi h:
V=N∪T∪ {X, $, Y }
∪ {(Ei, j)|Ei∈N0∪T∪ {$},1≤i≤n+ 1,0≤j≤n+ 1}
∪ {(Xi, j)|1≤i≤n+ 1,0≤j≤n+ 1},
µ= [0[1]1[2]2[3]3[4]4[5]5]0,
M1={X$S|Sis he axiom in G},
Mi=∅, o all i= 0,2, . . . , 5.
Le Π be gi en wi h he ollowing se s o p e-dynamical ules:
D1={S→wY @2|S→w∈P} ∪ {C→λ@4,$→λ@2}
∪ {Ei→(Ei,0)@3|Ei∈N0∪T∪ {$},1≤i≤n+ 1};
D2={Y→λ@1, A →λ@1, X →@0λ};
D3={X→@4(Xi,0) |1≤i≤n+ 1}
∪ {(Xi, j)→@4(Xi, j + 1) |0≤j < i ≤n+ 1};
D4={(Ei, j)→(Ei, j + 1)@3|0≤j < i ≤n+ 1}
∪ {(Ei, i)→λ@5|1≤i≤n+ 1} ∪ {B→λ@2};
D5={(Xi, i)→@1XEi|1≤i≤n+ 1}.
97
The sys em wo ks as ollows. Memb anes 1, 2, 4 a e used o simula ing he p oduc ions
in P, and memb anes 3, 4, and 5 a e used o pe o ming he o a ion o he igh mos
symbol in he cu en s ing. Memb ane 2 is also used o send he ecei ed s ings ou side
he sys em. No ice ha memb ane 4 akes pa bo h in o a ing he symbols and in
simula ing he ule ABC →λ. No ules a e gi en o he skin memb ane.
Symbols (Ei, j) and (Xi, j) a e used in making he o a ion o Ei∈N0∪T∪ {$} om
he igh end o he le end o he s ing. Numbe jin (Ei, j) is used as a coun e wi h
alue junde he o a ion, o gua an ee ha i we dele e (Ei, i) om he igh end o he
s ing, hen we co ec ly append he same symbol, Ei, o i s le end.
Le us assume now ha a some momen a s ing o he o m Xα$zcan be ound in
memb ane 1, o α∈(N0∪T)∗and z=z1Sz2o z=z3, wi h z1, z2, z3∈(N0∪T)∗. A
he i s s ep o he unc ioning, we ha e α=λand z=S.
Then he ollowing cases a e possible:
1. =S. We ha e o use a ule S→wY @2, which simula es he co esponding
p oduc ion S→win P and sends he s ing o memb ane 2. He e we can apply he ule
Y→λ@1, which sends he s ing back o memb ane 1. Then, i he igh mos symbol
o he new s ing is S, he p ocess is epea ed, o he wise he o a ion o a symbol o he
dele ion o symbol Ccan ollow. No e ha a any ime, in memb ane 2, also he ule
X→@0λcan be used causing he cu en s ing o exi he skin memb ane. Anyway,
since he sys em is ex ended, only he s ings o e he e minal alphabe Twill con ibu e
o he gene a ed language.
2. =Ei, o Ei∈N0∪T. In his case we can ob ain he s ing Xα$z0(Ei,0), wi h z0
such ha z=z0 , and we send i o memb ane 3, whe e he o a ion o Ei, he igh mos
symbol o he s ing will s a . I =C, hen he simula ion o he ule ABC →λ
can also ollow, since we can use he ule C→λ@3. A e he applica ion o his ule,
he s ing is o wa ded o memb ane 4, whe e he only ule applicable a his momen is
B→λ@2.I his ule is success ully applied, hen he s ing is sen o memb ane 2, whe e
A→λ@1can be used a his s ep (again, i we apply he o he applicable ule X→@0λ,
hen he s ing will no be pa o he gene a ed language). A e applying his ule, he
s ing a i es a memb ane 1. I hese s eps canno be pe o med a e each o he , hen
he compu a ion hal s and no e minal s ing is gene a ed.
3. = $. In his case he e a e wo possibili ies: by applying he ule En+1 →
(En+1,0)@5we s a he mo e o $ om he end o he s ing o i s beginning (a o a ion),
o by using $ →λ@2we inish he compu a ion in wo s eps. In he la e case symbol $
is e ased and he s ing is sen o memb ane 2, whe e Xis e ased and he s ing is sen
ou side he sys em.
Le us explain in mo e de ails how he symbols a e o a ed. Suppose ha a some
compu a ion s ep s ing Xα$z0(Ei,0) can be ound in memb ane 3. Then only ule X→
@4(Xj,0) can be applied a his s ep and a e he applica ion he s ing (Xj,0)α$z0(Ei,0)
is sen o memb ane 4. In his memb ane he only ule applicable a his momen is
(Ei, j)→(Ei, j + 1)@3, hen he ob ained s ing (Xj,0)α$z0(Ei,1) e u ns o memb ane
3 whe e we inc emen he coun e in (Xj,0). A e ha , he s ing (Xj,1)α$z0(Ei,1)
e u ns o memb ane 4. Repea ing he p ocedu e, he coun e is inc emen ed. A e some
s eps he ollowing h ee cases can occu :
1. Case i > j. When (Xj, j)α$z0(Ei, j) is sen o memb ane 3, hen he compu a ion
s ops wi hou gene a ing a s ing because i s ule (Xj, i)→@4(Xj, i + 1) can be applied
only i i < j.
2. Case i < j. When he s ing (Xj, i)α$z0(Ei, i) eaches memb ane 4, hen symbol
98
(Ei, i) is e ased by using ule (Ei, i)→λ@5and he s ing (Xj, i)α$z0is sen o memb ane
5. He e no ule can be applied because j6=iand hus he compu a ion abo s.
3. Case i=j. A some momen in memb ane 4 a s ing o he o m (Xi, i)α$z0(Ei, i)
can be ound. Then only ule (Ei, i)→λ@5can be applied which e ases he igh mos
symbol and sends he s ing (Xi, i)α$z0 o memb ane 5. In his memb ane, by applying
he ule (Xi, i)→@1XEi,XEiis appended o he le end o he s ing (co esponding
o he p e iously e ased symbol (Ei, i)) and hen XEiα$z0is sen o memb ane 1. Thus,
he o a ion o symbol Eiis comple ed.
The p ocess can be i e a ed. When a s ing Xα, α ∈(N0∪T)∗, is sen o memb ane
2 (a e using he ule $ →λ@2on he s ing Xα$ in memb ane 1), hen Xis e ased and
he s ing exi s he sys em. I such s ing is a e minal one, ha is α∈T∗, hen i will be
a membe o he gene a ed language. Hence, L(Π) = L(G). 2
The nex s a emen demons a es ha by using bo h classical e olu ion ules and p e-
dynamical ules, a smalle numbe o memb anes is needed o ob ain he compu a ional
comple eness.
Theo em 2 EGemP5(MP i, n(in/ou )) = EGemP∗(MP i, n(in/ou )) = RE.
P oo . Analogously o he p e ious s a emen , by [2] we should p o e only he
inclusion RE ⊆EGemP5(MP i, n(in/ou )). To his aim, we modi y he cons uc ion used
in he p oo o Theo em 1, ha is, o any ph ase-s uc u e g amma G= (N, T, S, P),
gi en in he Ge e no mal o m, we de ine a simula ing ex ended gemma ing P sys em
consis ing o i e memb anes, whe e bo h classical e olu ion ules (wi h a ge he e only)
and p e-dynamical ules can be p esen and also he me a-p io i y ela ion is de ined.
We cons uc he simula ing ex ended gemma ing P sys em o deg ee 5 as ollows:
Π = (V, T, µ, M0, . . . , M4,(C0, D0),(C1, D1), . . . , (C4, D4)),
whe e:
V=N∪T∪ {X, $}
∪ {(Ei, j)|Ei∈N0∪T∪ {$},1≤i≤n+ 1,0≤j≤n+ 1}
∪ {(Xi, j)|1≤i≤n+ 1,0≤j≤n+ 1},
µ= [0[1]1[2]2[3]3[4]4]0,
M1={X$S|Sis he axiom in G},
Mi=∅, o all i= 0,2,3,4.
Le Π be gi en wi h he ollowing se s o ules:
C1={S→(w, he e)|S→w∈P};
Ci=∅ o i= 0,2,3,4;
D0=∅;
D1={C→λ@3,$→λ@2}
∪ {Ei→(Ei,0)@2|Ei∈N0∪T∪ {$},1≤i≤n+ 1};
D2={X→@3(Xi,0) |1≤i≤n+ 1}
∪ {(Xi, j)→@3(Xi, j + 1) |0≤j < i ≤n+ 1}
99
∪ {X→@0λ};
D3={(Ei, j)→(Ei, j + 1)@2|0≤j < i ≤n+ 1}
∪ {(Ei, i)→λ@4|1≤i≤n+ 1} ∪ {B→λ@4};
D4={(Xi, i)→@1XEi|1≤i≤n+ 1}∪{A→λ@1}.
Symbols X, (Xi, j),(Ei, j), and $, as in he p e ious p oo , a e auxilia y symbols used
in he o a ion o he symbols, $ is he ma ke symbol indica ing he beginning o he
simula ed s ing o G. Analogously, le us deno e he elemen s in ({A, B, C} ∪ T) by
E1, . . . , En, n ≥1,and le En+1 be a no a ion o $.
Now we explain how he sys em Π wo ks and how he s ings gene a ed by Ga e
gene a ed by Π.
I is easy o see ha in he i s phase o he unc ioning o Π, memb ane 1 uses i s
classical e olu ion ules and gene a es a wo d o he o m X$α, whe e α∈(N0∪T)∗.
Du ing hese s eps, no ac ion is pe o med in he o he memb anes. Then, a second phase
o he unc ioning ollows, wi h he ollowing possibili ies:
1. I he igh mos symbol o αis C, hen he simula ion o he ule ABC →λ∈P
can s a in memb ane 1, by applying he p e-dynamical ule C→λ@3. Then Cis dele ed
om he igh -end o αand he s ing is o wa ded o memb ane 3. In his memb ane he
only applicable ule is B→λ@4,which dele es he igh mos symbol, B, o he s ing.
Then, he new s ing is sen o memb ane 4, whe e A→λ@1can be applied: a e
emo ing symbol A om i s igh -end, he s ing e u ns o memb ane 1 and he p ocess
can be epea ed. I any o hese s eps ails, hen he P sys em hal s wi hou a e minal
wo d as an ou pu . No e ha in memb ane 2, a any ime, we can also use he ule
X→@0λwhich sends he s ing ou side he skin memb ane; anyway, i he s ing is no
consis ing o e minal symbols only, hen i will no con ibu e o he gene a ed language.
2. I espec i ely om whe he o no he igh mos symbol o αis C, a o a ion o a
symbol om ({A, B, C, $}∪T) can s a in memb ane 1, by applying a ule Ei→(Ei,0)@2,
o 1 ≤i≤n+ 1.Then, exac ly in he way as in he p e ious p oo , by he in e play
o memb anes 2, 3, and 4, symbol Eiis o a ed. No ice ha he p ocedu es o dele ing
subs ing ABC, om he igh -end o he s ing and he o a ion o symbols Eido no
in e e e each o he .
Combining he wo p ocedu es, ha is, dele ing subs ing ABC om he igh -end
o he s ing and o a ing he symbols, ei he we ob ain a s ing o he o m Xw$ wi h
w∈T∗in memb ane 1 o he sys em hal s wi hou a e minal ou pu . I he i s case
holds, hen he s ing is o wa ded o memb ane 2, and a e hen ou side he sys em, and
he success ul compu a ion ends.
By he a gumen a ion abo e, we can easily see ha L(Π) = L(G) holds. 2
4 Conclusions and Open P oblems
In he p e ious sec ion we imp o ed he known size bounds conce ning wo ypes o ex-
ended gemma ing P sys ems. I is an open ques ion whe he o no hese bounds a e
sha p. Mo eo e , i would be in e es ing o gi e sha p bounds on he numbe o mem-
b anes in ex ended gemma ing P sys ems de e mining he class o ma ix languages, he
class o ET0L languages, ha is, p ope subclasses o he ecu si ely enume able language
class. Simila ly, we can ask wha can we say abou he size and he powe o non-ex ended
100