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