Size and Power of Extended Gemmating P Pystems

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