On P Systems with Promoters/Inhibitors

On P Sys ems wi h P omo e s/Inhibi o s Mihai IONESCU 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] D ago¸s SBURLAN Depa men o Compu e Science O idius Uni e si y o Cons an ¸a Bd. Mamaia 124, Cons an ¸a, Romˆania E-mail: [email p o ec ed] Abs ac . This a icle shows how he compu a ional uni e sali y can be eached by using P sys ems wi h objec ew i ing con ex - ee ules, p omo - e s/inhibi o s and one ca alys . Bo h gene a i e and accep ing cases a e s ud- ied. Some examples ha illus a e he heo e ical issues a e also p esen ed. 1 In oduc ion P sys ems ep esen a class o dis ibu ed/pa allel compu ing de ices whose unc ioning is inspi ed om he beha io o molecules and li ing cells. The e, chemical compounds a e p ocessed in a massi e pa allel manne inside a compa men al s uc u e o memb anes ha con ol he subs ances exchanges be ween egions hey delimi . The eac ions ha ake place inside such a biological s uc u e can be o mally desc ibed by coope a i e ules. One pa icula case is ha o ca aly ic ules which model he biological eac ions ha can ake place only wi h he help o ce ain enzyma ic p o eins (which pa icipa e in eac ions and emain unmodi ied a e hey occu ). Ano he impo an ype is ha o p omo ed/inhibi ed eac ions ha happen in he p esence/absence o ce ain chemicals which a e no di ec ly implied in eac ions. In his abs ac , symbolic, ma hema ical amewo k i is in e es ing o see which is he compu a ional powe when “low” coope a ion ea u es a e used. In his sense, as i was shown in [4], P sys ems wi h con ex - ee and ca aly ic ules wi h only wo dis inc ca alys s a e compu a ional uni e sal. Also, in [1] a model wi h con ex - ee ules, one ca alys and p omo e s a he le el o ules s shown o be uni e sal. In his pape we explo e he compu a ional powe o he sys ems wi h con ex - ee ules, ca aly ic ules wi h one ca alys and p omo e s/inhibi o s. Bo h gene a i e and accep ing cases will be s udied he e. Meanwhile, we in oduce he egula ed ew i ing mechanism o egula ly con olled con ex - ee g amma s o as a ool in he s udy o P sys ems. 264 2 P elimina ies 2.1 Regula ed Rew i ing In any Chomsky g amma , a some gi en s ep in a de i a ion one can use o ew i ing any applicable ule in any desi ed place o he sen en ial o m. In o de o es ic his nonde e minism some egula ing mechanisms, which can con ol he de i a ion p ocess, we e conside ed. Using such egula ions we can a i e o compu a ional uni e sali y e en i we use con ex - ee g amma s as a co e gene a i e de ice. In li e a u e he e a e many ypes o egula ions which es ic he use o ules in a Chomsky g amma (see [3], [8]). He e we will p esen only egula ly con olled g amma s wi h appea ance checking and λ– ules. A egula ly con olled con ex - ee g amma wi h appea ance checking is a 6- uple G C = (N, T, P, S, R, F ) whe e N,T,P, and Sa e speci ied as in con ex - ee g amma , R is a egula language o e P, and Fis a subse o P. Fo a ule p=A→w∈Pand x, y ∈V∗ Gwe w i e x=⇒ac pyi ei he 1. x=x1Ax2and y=x1wx2, o 2. x=y,Adoes no appea in x, and p∈F. The language L(G) gene a ed by Gwi h appea ance checking consis s o all wo ds w∈T∗such ha he e is a de i a ion S=⇒ac p1w1=⇒ac p2w2· · · =⇒ac pnwn=w wi h p1p2· · · pn∈R. We say ha Gis a egula ly con olled g amma wi hou appea ance checking i F=∅. By L(λ C), L(λ Cac), L( C), and L( Cac) we deno e he amilies o languages gene - a ed by egula ly con olled g amma s (wi hou appea ance checking), egula ly con olled g amma s wi h appea ance checking, egula ly con olled g amma s wi hou e asing ules (and wi hou appea ance checking), and egula ly con olled g amma s wi h appea ance checking and wi hou e asing ules, espec i ely. The ollowing esul s s and: L(CF)⊂ L( C)⊆ L(λ C)⊂ L(λ Cac) = L(RE). In e es ing o he scope o he p esen pape is he las equali y, L(λ Cac) = L(RE), since we will simula e a egula ly con olled g amma wi h appea ing checking and λ– ules wi h P sys ems in o de o show hei uni e sali y. 2.2 Regis e Machines We will use in ou pape he powe o Minsky’s egis e machine [6], ha is why we ecall he e his no ion. Such a machine uns a p og am consis ing o numbe ed ins uc ions o se e al simple ypes. Se e al a ian s o egis e machines wi h di e en numbe o egis e s and di e en ins uc ions se s we e shown o be compu a ionally uni e sal (see [6] o some o iginal de ini ions and [5] o he de ini ion we use in his pape ). An- egis e machine is a cons uc M= (n, P, i, h), whe e: 265 •nis he numbe o egis e s, •Pis a se o labeled ins uc ions o he o m j: (op( ), k, l), whe e op( ) is an ope a ion on egis e o M, and j, k, l a e labels om he se Lab(M) (which numbe s he ins uc ions in a one- o-one manne ), •iis he ini ial label, and •his he inal label. The machine is capable o he ollowing ins uc ions: (add( ), k, l) : Add one o he con en s o egis e and p oceed o ins uc ion ko o ins uc ion l; in he de e minis ic a ian s usually conside ed in he li e a u e we demand k=l. (sub( ), k, l) : I egis e is no emp y, hen sub ac one om i s con en s and go o ins uc ion k, o he wise p oceed o ins uc ion l. hal : This ins uc ion s ops he machine. This addi ional ins uc ion can only be assigned o he inal label h. A de e minis ic m- egis e machine can analyze an inpu (n1, ..., nα)∈Nα 0in egis e s 1 o α, which is ecognized i he egis e machine inally s ops by he hal ins uc ion wi h all i s egis e s being emp y ( his las equi emen is no necessa y). I he machine does no hal , he analysis was no success ul. 2.3 P Sys ems P e equisi es A P sys em (o deg ee m≥1) wi h symbol–objec s and ew i ing e olu ion ules is a cons uc Π = (V, C, µ, w1, . . . , wm,(R1, ρ1), . . . , (Rm, ρm), i0), whe e: •Vis he alphabe o Π; i s elemen s a e called objec s; •C⊆Vis he se o ca alys s; •µis a memb ane s uc u e consis ing o mmemb anes labeled 1,2,···, m; •wi, 1 ≤i≤m, speci y he mul ise s o objec s p esen in he co esponding egions ia he beginning o a compu a ion; •Ri, 1 ≤i≤m, a e ini e se s o e olu ion ules o e Vassocia ed wi h he egions 1,2, . . . , m o µ, and ρiis a pa ial o de ela ion o e Ri(a p io i y ela ion); hese e olu ion ules a e o he o m a→ o ca →c , whe e ais an objec om V−C and is a s ing o e (V−C)×({he e, ou , in}) (In gene al, he a ge indica ions he e,ou ,in a e w i en as subsc ip s o objec s om V.); •i0is a numbe be ween 0 and mand speci ies he ou pu memb ane o Π (in case o 0, he en i onmen is used o he ou pu ). 266 S a ing om he o iginal model some a ian s we e p oposed (see [7]). One o hem is P sys ems wi h p omo e s/inhibi o s and was in oduced in [1]. In he case o p omo e s, he ules ( eac ions) a e possible only in he p esence o ce ain symbols. An objec ais a p omo e o a ule u→ , and we deno e his by u→ |a, i he ule is ac i e only in he p esence o objec a. An objec bis an inhibi o o a ule u→ , and we deno e his by u→ |¬b, i he ule is ac i e only i inhibi o bis no p esen in he egion. In pa icula , p omo e s/inhibi o s hemsel es can e ol e acco ding o some ules. The di e ence be ween ca alys s and p omo e s consis s in he ac ha he ca alys s di ec ly pa icipa e in ules (bu a e no modi ied by hem), and hey a e coun ed as any o he objec s, so ha he numbe o applica ions o a ule is as big as he numbe o copies o he ca alys , while in he case o p omo e s, he p esence o he p omo e objec s makes i possible o use he associa ed ule as many imes as possible, wi hou any es ic ion; mo eo e , he p omo ing objec s do no necessa ily di ec ly pa icipa e in he ules. As a consequence, one can no ice ha he ca alys s inhibi s he pa allelism o he sys em while he p omo e s/inhibi o s only guide he compu a ion p ocess. The P sys em wi h he men ioned ea u es s a s o e ol e om an ini ial con igu a ion, by pe o ming all ope a ions in a pa allel way, o all applicable ules, o all occu ences o objec s in he egion associa ed wi h he ules, o all egions a he same ime and acco ding o a uni e sal clock. A compu a ion is success ul i and only i i hal s, meaning ha no ule is applicable o he objec s p esen in he inal con igu a ion. The esul o a hal ing compu a ion is he numbe o objec s p esen in he egion i0in he hal ing con igu a ion. The se o all numbe s cons uc ed in his way by a sys em Π is deno ed by N(Π). Fo such kind o P sys ems we will use he ollowing no a ion: NOPm(α, β), α ∈ {ncoo, coo}∪{ca k|k≥0}, β ∈ {p oR, inhR} o deno e he amily o se s o na u al numbe s gene a ed by P sys ems wi h a mos mmemb anes, e olu ion ules ha can be non-coope a i e (ncoo), coope a i e (coo), o ca aly ic (ca k), using a mos kca alys s, and p omo e s (p oR) o inhibi o s (inhR) a he le el o ules. Also, we may conside as he esul o a hal ing compu a ion he ec o Ψ(w) ( he ec o o mul iplici ies o objec s) whe e wis he mul ise p esen in he egion i0in he hal ing con igu a ion. In his case, he se o all ec o s cons uc ed in his way by a sys em Π is deno ed by Ps(Π). We will use also he ollowing no a ion: PsIPm(α, β), α ∈ {ncoo, coo} ∪ {ca k|k≥0}, β ∈ {p oR, inhR}, o deno e he amily o se s o ec o s o na u al numbe s gene a ed by P sys ems wi h a mos mmemb anes, e olu ion ules ha can be non-coope a i e (ncoo), coope a i e (coo), o ca aly ic (ca k), using a mos kca alys s, and p omo e s (p oR) o inhibi o s (inhR) a he le el o ules. He e, Is ands o P sys ems wi h in e nal inpu . In his pape we will show how he egula ly egula ed con ex - ee g amma s wi h appea ance checking can be used o p o e he compu a ional uni e sali y o such ype o P sys ems. Also we will also s udy he de e minis ic P sys ems accep ing se s o ec o s o na u al numbe s. We indica e [1] o mo e de ails conce ning P sys ems wi h p omo e s/inhibi o s. 267 0→0ou 1→1ou c 0→00Aou c00→c0ou 1→10 10→100Bou c100 →c1ou A→A0 0→0ou |A0 A0→A00 0→λ|A00 A00 →λ B→B0 1→λ|B0 B0→B00 1→1ou |B00 B00 →λ ' & $ % 1 2 3 ' & $ % ' & $ % Figu e 1: Simula ion o he AND ga e using p omo e s and one ca alys 3 Some Rele an Examples In his sec ion we will p esen some examples o P sys ems compu ing some “sensi i e” asks using abo e in oduced ypes o P sys ems. Fi s we will cons uc a P sys em wi h p omo e s ha , ha ing as inpu wo alues, say 0 and/o 1, compu es he and ope a ion (see Figu e 1). Fo mally, we de ine he ollowing P sys em ΠAND = (V, C, µ, w1, w2, w3, R1, R2, R3,0), whe e: •V={0,1,00,10,100, A, A0, A00, B, B0, B00 , c}; •C={c}; •µ= [3[2[1]1]2]3; •w1=w3=∅,w2={c}; •R1={1→1ou , 0 →0ou }; R2={0→00Aou ,c00→c0ou , 10→100Bou , 1 →10, c100 →c1ou }; R3={A→A0, 0 →0ou |A0,A0→A00, 0 →λ|A00 , A00 →λ,B→B0, 1 →λ|B0,B0→B00, 1→1ou |B00 ,B00 →λ}. The simula ion o he AND ga e uses he ca alys c o inhibi he pa allelism and o sepa a e he en ance ime o objec s 0 and 1 in o egion 3. Acco ding o he en ance ime, objec s will be ei he dele ed, o sen ou in o he en i onmen . Mo e speci ically, i we conside ha ini ially we had wo objec s 0 inside egion 2, he ule 0 →00Aou is execu ed. I s ole is o in oduce he objec Ain o egion 3 o se up he “ igh ” con igu a ion o he egion. Nex , in egion 2 he only applicable ule is c00→c0ou , which will in oduce one objec 0 in o egion 3. A he same ime, in egion 3 he ule A→A0is execu ed. Now, we 268 c, an, bm ca →ca0d|¬a0 cb →cb0d|¬b0 a0→Aou |¬b b0→Bou |¬a d→λ a0→λ|¬d b0→λ|¬d 1 2 ' & $ % ' & $ % Figu e 2: In ege sub ac ion using inhibi o s and one ca alys will ha e in egion 3 he objec s A0and 0, and he ules ha will be applied a e 0 →0ou |A0 and A0→A00. These ules gua an ee ha an objec 0 is sen ou in o he en i onmen . In he mean ime, in egion 2, he emaining objec 00 eac s wi h he ca alys cand an objec 0 will be in oduced in o egion 3 ( he ule used is again c00→c0ou ). He e, he objec 0 will ind a di e en con ex since now, in egion 3 he e is no objec A0. The e o e, he ules 0 →λ|A00 and A00 →λa e applied, hence he ini ial con igu a ion o he sys em is es o ed. Basically, a simila me hod s ands o he o he cases, wi h some mino changes: objec s 1 en e in o egion 3 wi h one compu a ional delay (because o he ule 1 →10 p esen in egion 2) in o de no o in luence he p ocesses execu ing in egion 3; he i s objec 1 ha en e s in o egion 3 is dele ed (as opposed o he abo e case when he i s objec 0 ha a i es in egion 3 is sen ou ) by using he ule 1 →λ|B0. Recall ha he memb ane 1 can be en i ely a oided, i s ole being only o speci y he en y poin o he inpu . Also, he esul o compu a ion is sen ou in o en i onmen e en i i is ac ually ob ained in egion 3. This ea u es a e use ul when we wan o connec ga es in o ci cui s (see [2] o mo e de ails). The second example (see Figu e 2) uses con ex - ee ules, inhibi o s and one ca alys o compu e he a i hme ic di e ence be ween he ini ial mul iplici y o wo dis inc objec s, p esen a he beginning o compu a ion in o an “inpu ” egion. Fo mally, we de ine he ollowing P sys em Πsub ac ion = (V, C, µ, w1, w2, R1, R2,2), whe e: •V={a, b, a0, b0, d, A, B, c}; •C={c}; •µ= [2[1]1]2; •w1={c, an, bm},w2=∅; •R1={ca →ca0d|¬a0,cb →cb0d|¬b0,a0→Aou |¬b, b0→Bou |¬a,d→λ,a0→λ|¬d,b0→λ|¬d}; R2=∅. 269 The sys em s a s he compu a ion ha ing in o he inpu memb ane 1 a ca alys cand he objec s an,bn, whose mul iplici y we wan o sub ac . The esul o compu a ion is sen o egion 2 and i is ep esen ed by: •An−mi n > m; •Bm−ni m > n; •no objec is sen o egion 2 meaning ha m=n. The sys em wo ks as ollows: while he e a e s ill objec s aand b, hey a e dele ed in pai s, i e a i ely, up o a momen when he e a e no mo e objec s a, o ins ance (o objec s b). A ha momen , he low o compu a ion changes and as a esul , also i e a i ely, he emaining objec s b(o objec s a, espec i ely) a e send ou . Du ing he compu a ion, he p omo e s con ol he de i a ion p ocess, while he ca alys inhibi s he pa allelism. Fo a be e unde s anding we p esen he con igu a ion able o he case when bo h objec s aand ba e p esen simul aneously in o he inpu memb ane. egion 1 egion 2 0c, an, bm ca →ca0d|¬a0 1c, an−1, bm, a0, d cb →cb0d|¬a0 d→λ 2c, an−1, bm−1, a0, b0, d d→λ 3c, an−1, bm−1, a0, b0 a0→λ|¬d b0→λ|¬d 0 0c, an−1, bm−1 ca →ca0d|¬a0 ··· ··············· ········· He e we ha e conside ed only he case when a he i s s ep an objec a eac s wi h he ca alys c. The esul o compu a ion emains unchanged (due o symme y easons) e en i , a he i s s ep, an objec b eac s wi h he ca alys c. When in he egion emain only objec s a, he con igu a ion able o he o hcoming compu a ions is: egion 1 egion 2 pc, ak ca →ca0d|¬a0 p+1 c, ak−1, a0, d a0→Aou |¬b0 d→λ 0 pc, ak−1A ca →ca0d|¬a0 ··· ··············· ········· The case when inside he egion 1 emain only objec s band he ca alys cis simila wi h he p e ious one, and has as esul he p oduc ion in o egion 2 o m−ncopies o objec s B. 270 Since in bo h examples we ha e used some con ex -sensing ea u es we may conjec u e ha bo h P sys ems wi h p omo e s and P sys ems wi h inhibi o s, using only one ca alys , a e compu a ional uni e sal. Indeed, he ollowing sec ion will be dedica ed o hese issues and, he e, we will show how any ecu si ely enume able se o na u al numbe s can be ob ained using hese ypes o P sys ems. 4 Uni e sali y Resul s 4.1 Compu a ional Uni e sali y – The Gene a ing Case He e, we p esen wo uni e sali y esul s conce ning P sys ems wi h p omo e s o in- hibi o s a he le el o ules. The p oo s a e based on he simula ions o egula ly con- olled con ex - ee g amma s wi h appea ance checking o which he equi alence wi h RE s ands. We deno e by NOPm(ca , p oR), he amily o se s N(Π) compu ed by sys- ems wi h a mos mmemb anes, 1 ca alys (say c) and objec s as p omo e s. By NRE we deno e he amily o Tu ing compu able se s o numbe s. Theo em 1 NOP2(ca 1, p oR) = NRE. P oo . We will conside o his p oo he implica ion NRE ⊆NOP2(ca , p oR); he o he way a ound is a long, bu s aigh o wa d cons uc ion. Le G eg = (N eg, T eg, P eg, S eg) be a egula g amma gene a ing he egula se L eg. We deno e by he numbe o ules in P eg. The ules o P eg a e enume a ed as i: (Mi→piQi) o i: (Mi→pi) wi h 1 ≤i≤ , whe e Mi∈N eg and pi∈T eg ∀1≤i≤ . Fo any such g amma G eg we can cons uc an equi alen igh –linea g amma G0= (N0, T0, P0, S0) in he ollowing way: T0=T eg, S0=S eg, N0=N eg ∪ {M(i,1), M(i,2), M(i,3) |1≤i≤ }. Fo any ule i: (Mi→piQi)∈P eg o i: (Mi→pi)∈P eg, 1 ≤i≤ we will ha e in P0 he sequence o ules: Mi→M(i,1),M(i,1) →M(i,2),M(i,2) →M(i,3),M(i,3) →piQi, Mi→M(i,1),M(i,1) →M(i,2),M(i,2) →M(i,3),M(i,3) →pi espec i ely. Mo eo e , P0does no con ain o he ules excep ing he ules conside ed abo e. In o he wo ds, he only di e ence be ween he wo g amma s is ha he p oduc ion o a new e minal in g amma G0is done a e each ou h s ep o a de i a ion. Now le us cons uc a P sys em which simula es he de i a ion p ocess o a egula ly con olled g amma wi h appea ance checking. The sys em will use only wo memb anes, one ca alys and p omo e s. The inne mos memb ane will con ain he gene a i e mecha- nism and he esul s o compu a ion will be send ou o he skin memb ane which will be he ou pu memb ane o he sys em ( he eason is ha he ca alys is used du ing he com- pu a ion o inhibi he pa allelism and i canno be emo ed, he e o e we canno ob ain he numbe 0 as he esul o compu a ion i we use only one memb ane). In wha ollows 271 we will discuss only he ules in he inne mos memb ane since he skin memb ane does no execu e any ask (i s ole is only o collec he objec s ob ained du ing compu a ion). The p omo e s will be gene a ed by a mechanism like he one p esen ed abo e (p o- mo e s will be ac ually e minal symbols om T0and, he e o e, hey will be gene a ed a each o h s ep). They will pe mi he execu ion o “con ex - ee” ules in he “ igh ” o de – he o de gi en by he egula mechanism. In o de o co ec ly simula e he appea ance checking mechanism we ha e o modi y he ules in he g amma G0such ha we eplace each ule o ype M(i,3) →piQiby ules o ype: M(i,3) →piQi o M(i,3) →piQiadepending on how he objec piindica es a ule om F(in he egula ly con olled g amma de ini ion, he se F⊂P ep esen s he appea ance checking se o ules; we will use he objec a o iden i y ha a ule wi h he co esponding label piis in he appea ance checking se ; i no , we will p oduce in he ule he objec ). We will conside also he same cons uc ion o he ules in G0o ype M(i,3) →pi, i.e., M(i,3) →pi o M(i,3) →pia. This means ha , in he de ini ion o ou P sys em, o he inne memb ane, we will ha e ules o he ollowing ypes: •Mi→M(i,1) , M(i,1) →M(i,2) , M(i,2) →M(i,3) , M(i,3) →piQi i piis no a label in he appea ance checking se ; •Mi→M(i,1) , M(i,1) →M(i,2) , M(i,2) →M(i,3) , M(i,3) →piQiai piis a label in he appea ance checking se ; •Mi→M(i,1) , M(i,1) →M(i,2) , M(i,2) →M(i,3) , M(i,3) →pi i piis no a label in he appea ance checking se ; •Mi→M(i,1) , M(i,1) →M(i,2) , M(i,2) →M(i,3) , M(i,3) →piai piis a label in he appea ance checking se . Up o his momen , we only ha e conside ed he egula mechanism which gene - a es labels indica ing he con ex - ee ules ha should be applied. Le us deno e by GCF = (NCF , TCF , PCF , SCF ) a con ex - ee g amma wi h p oduc ions labeled wi h he elemen s o T eg. Now we will discuss how we can simula e (by using P sys ems means) he applica ion o a con ex - ee ule p: (A→α) indica ed by he egula mechanism. Fo a con ex - ee ule (p: (A→α)) ∈GCF we will ha e in ou P sys em he ollowing sequence o ules: cA →cDα|p, p→p0, p0→λ|D, D→λ. He e, we ha e conside ed, wi hou loosing he gene ali y, ha α∈(N∪Tou )∗meaning ha i we apply he ule p: (A→α) we will send o he ou pu egion he e minal symbols ( ecall ha we a e in e es ed only in he numbe o objec s). I p omo e p, objec A, and ca alys ca e p esen a a ce ain momen oge he , hen hey will eac only once in wo consecu i e compu a ional s eps. This is due o he ac ha he p omo e pis changed (p→p0) in he same momen wi h he execu ion o he ule cA →cDα|p. Mo eo e , he p esence o he ca alys cin he ule inhibi s he pa allelism (we wan ha in one “ ound” he ule A→α o be applied only once and no o all occu ences o objec A ha may exis in he egion). Now, in o de o be su e ha he ule cA →cDα|pwas execu ed an objec Dis c ea ed; i will help o dele e he objec p0p esen in memb ane (which i no dele ed can cause p oblems in u he s eps). The objec Dwill be also dele ed by he ule D→λ. 272 5 Conclusion As i can be seen om he p oo s o i s wo heo ems conce ning p omo e s/inhibi o s a he le el o ules, he use o egula ly con olled con ex - ee g amma wi h appea - ance checking is use ul o show compu a ional uni e sali y when we a e no in e es ed in minimizing he numbe o p omo e s/inhibi o s. P ac ically, in bo h p oo s we ha e used a numbe o p omo e s/inhibi o s equal wi h he numbe o e minals in he egula g amma which con ols he de i a ion p ocess. Fo he las wo heo ems we succeeded wi h a P sys em o simula e in a de e minis ic manne a de e minis ic egis e machine. The e we disco e ed ha , in case o p omo ed P sys ems, 4 ∗np omo e s a e enough o ecognize PsRE ∩Nn; in case o P sys ems wi h inhibi o s, he numbe o inhibi o s used o ecognize PsRE ∩Nnwas 4 ∗n+ 3. Fo all heo ems p esen ed, an impo an aspec is ha he p omo e s/inhibi o s may eac a he same ime as he ules hey p omo e/inhibi . This ac , joined wi h he use o one ca alys which inhibi s he pa allelism, makes his ypes o P sys ems compu a ional uni e sal. Se e al p oblems ega ding his opic s ill emain open. In he de e minis ic a ian o ecognizing P sRE ∩Nn he e is no known which is he lowe bound o symbols ha , ac ing as p omo e s/inhibi o s, make he P sys em model uni e sal (when one ca alys is used). Also, he e is no known which is he compu a ional powe o P sys ems wi h p omo e s/inhibi o s a he le el o ules when no ca alys is used. Acknowledgmen s. The wo k o he i s au ho was suppo ed by he FPU ellow- ship om he Minis e io de Educacion, Cul u a y Depo e. The wo k o he second au ho was possible due o a doc o al g an om Agencia Espanola de Coope acion In e nacional, Spanish Minis y o Fo eign A ai s. Re e ences [1] P. Bo oni, C. Ma ´ın-Vide, Gh. P˘aun, G. Rozenbe g, Memb ane Sys ems wi h P o- mo e s/ Inhibi o s, Ac a In o ma ica,38,10 (2002), 695–720. [2] R. Ce e chi, D. Sbu lan, Simula ing Boolean Ci cui s wi h P Sys ems, Wo kshop on Memb ane Compu ing WMC-Ta agona 2003 (A. Alhazo , C. Ma ´ın-Vide, G. P˘aun, eds), TR 28/03, URV Ta agona, 2003. [3] J. Dassow, Gh. P˘aun, Regula ed Rew i ing in Fo mal Language Theo y, Sp inge - Ve lag, Be lin, 1989. [4] R. F eund, L. Ka i, M. Oswald, P. Sosik, Compu a ionally Uni e sal P sSys ems wi h- ou P io i ies: Two Ca alys s A e Su icien , submi ed 2003. [5] S. Kh isna, A. P˘aun, Th ee Uni e sali y Resul s on P Sys ems, Wo kshop on Mem- b ane Compu ing WMC-Ta agona 2003 (A. Alhazo , C. Ma ´ın-Vide, G. P˘aun, eds),TR 28/03, URV Ta agona, 2003, 198–206. [6] M.L. Minsky, Fini e and In ini e Machines, P en ice Hall, EngleWood Cli s, 1967. [7] Gh. P˘aun, Memb ane Compu ing. An In oduc ion, Sp inge -Ve lag, Be lin, 2002. 279 [8] Gh. P˘aun, G. Rozenbe g, A Guide o Memb ane Compu ing, Theo e ical Compu e Science,287, 1 (2002), 73–100. [9] G. Rozenbe g, A. Salomaa, eds., Handbook o Fo mal Languages, Sp inge -Ve lag, Be lin, 1997. 280