T ading Pola iza ion o Bi-s able Ca alys s
in P Sys ems wi h Ac i e Memb anes
Ma io J. P´e ez-Jim´enez and F ancisco Jos´e Rome o-Campe o
Resea ch G oup on Na u al Compu ing,
Depa men o Compu e Science and A ificial In elligence,
Uni e si y o Se illa,
A da. Reina Me cedes s/n, 41012 Se illa, Spain
{Ma io.Pe ez, F ancisco-Jose.Rome o}@cs.us.es
Abs ac . In he las ime, se e al effo s ha e been made in o de o
emo e pola iza ions o memb anes om P sys ems wi h ac i e mem-
b anes; he p esen pape is a con ibu ion in his espec . In o de o
compensa e he loss o powe ep esen ed by a oiding pola iza ions, we
use bi-s able ca alys s. Pola iza ionless sys ems wi h ac i e memb anes
which use bi-s able ca alys s a e p o en o be compu a ionally comple e
and able o sol e efficien ly NP-comple e p oblems. In his pape we
p esen a solu ion o SAT in linea ime. In o de o illus a e he p e-
sen ed solu ion, we also p o ide a simula ion wi h CLIPS.
1 In oduc ion
In memb ane compu ing, P sys ems wi h ac i e memb anes a e specially sui able
o sol e efficien ly NP-comple e p oblems, because o he ac ha hey p o ide
memb ane di ision, inspi ed om cell di ision. By using his ope a ion, one can
c ea e an exponen ial numbe o memb anes (wo king space) in linea ime; in
his way, we ade space o ime o sol e NP-comple e p oblems ( his has been
epo ed o SAT, VALIDITY, Subse Sum, Knapsack, e c.).
One impo an ea u e o P sys ems wi h ac i e memb anes is he pola iza ion
o memb anes; each memb ane has an “elec ical cha ge”, posi i e (+), nega i e
(−) o neu al (0). Howe e , he elec ical cha ges a e no e y ealis ic om a
biological poin o iew. Because o his, se e al effo s a e being made in o de
o emo e he pola iza ions wi hou losing he uni e sali y and he efficiency.
This pape goes in o his di ec ion o esea ch: we emo e he pola iza ion o
he memb anes bu on he o he hand we use bi-s able ca alys s. This a ian
o P sys ems wi h ac i e memb anes is p o en o be compu a ionally comple e
and able o sol e NP-comple e p oblems like SAT in linea ime.
The pape is o ganized as ollows: Sec ion 2 in oduces bi-s able ca aly ic P
sys ems wi h ac i e memb anes wi hou cha ges as gene a ing de ices and as
ecognize de ices. In Sec ion 3 he complexi y classes o P sys ems a e b iefly
ecalled. Sec ions 4, 5, and 6 p esen a cellula solu ion in linea ime o he
SAT p oblem wi hin he amewo k o his a ian o P sys ems. In Sec ion 7
he p og amming language CLIPS is used o exhibi a simula ion o he designed
solu ion in o de o illus a e how i wo ks. Conclusions a e gi en in Sec ion 8.
2 Bi-s able Ca aly ic P Sys ems wi h Ac i e Memb anes
Wi hou Pola iza ions
Defini ion 1. A bi-s able ca aly ic P sys em wi h ac i e memb anes and wi hou
pola iza ions is a uple
Π=(Γ,K,H,µ,M1,...,Mp,R),
whe e:
1. p≥1is he ini ial deg ee o he sys em;
2. Γis he alphabe o symbol-objec s;
3. Kis a subse o Γ,K⊆Γ, such ha i c∈K hen c∈K( he elemen s o
Ka e called bi-s able ca alys s);
4. His a fini e se o labels o memb anes;
5. µis a memb ane s uc u e consis ing o pmemb anes labelled (no necessa ily
in a one- o-one manne ) wi h elemen s o H;
6. M1,...,Mpa e s ings o e Γ, desc ibing he ini ial mul ise s o objec s
associa ed wi h he egions o µ;
7. Ris a fini e se o e olu ion ules, o he ollowing o ms:
(a) [a→ω]h, o h∈H,a∈Γ−K, ω ∈(Γ−K)∗. This is an objec
e olu ion ule, associa ed wi h a memb ane labelled wi h hbu no di ec ly
in ol ing he memb ane.
(b) [ca →cω ]h,[ca →cω ]h,[ca →cω ]h,[ca →cω ]h, o h∈H,c∈K
and a∈Γ−K, ω ∈(Γ−K)∗(bi-s able ca aly ic e olu ion ules). Such
a ule is an objec e olu ion ule in ol ing bi-s able ca alys s, associa ed
wi h a memb ane labelled wi h h bu no di ec ly in ol ing he memb ane.
(c) a[]
h→[b]h, o h∈H,a, b ∈Γ−K(“send in” communica ion ules).
An objec om he egion immedia ely ou side a memb ane labelled wi h h
is in oduced in his memb ane, possibly ans o med in o ano he objec .
(d) [a]h→b[]
h, o h∈H,a, b ∈Γ−K(“send ou ” communica ion
ules). An objec is sen ou om memb ane labelled wi h h o he egion
immedia ely ou side, possibly ans o med in o ano he objec .
(e) [a]h→b, o h∈H,a, b ∈Γ−K(dissol ing ules). A memb ane
labelled wi h his dissol ed in eac ion wi h an objec . The skin is ne e
dissol ed.
( ) [a]h→[b]h[c]h, o h∈H,a, b, c ∈Γ−K(di ision ules o ele-
men a y memb anes). An elemen a y memb ane can be di ided in o wo
memb anes wi h he same label, possibly ans o ming some objec s.
No e ha , in con as o [2], he bi-s able ca alys s a e no always flip-flop-ing
om non-ba ed o ba ed e sions and back, bu also ules o he o m ca →cw
and ¯ca →¯cw a e allowed. The case when he ca alys s appea only in ules o
he o m ca →¯cw and ¯ca →cw is called es ic ed.
These ules a e applied acco ding o he ollowing p inciples:
•All he ules a e applied in pa allel and in a maximal manne . In one s ep,
one objec o a memb ane can be used by only one ule (chosen in a non
de e minis ic way), bu any objec which can e ol e by one ule o any o m,
should e ol e.
•I a memb ane is dissol ed, i s con en (mul ise and in e nal memb anes) is
le ee in he su ounding egion.
•I a he same ime a memb ane his di ided by a ule o ype (e) and he e
a e objec s in his memb ane which e ol e by means o ules o ype (a) and
(b), hen we suppose ha fi s he e olu ion ules o ypes (a) and (b) a e
used, and hen he di ision is p oduced. O cou se, his p ocess akes only
one s ep.
•The ules associa ed wi h memb anes labelled wi h ha e used o all copies o
his memb ane. A one s ep, a memb ane labelled wi h hcan be he subjec
o only one ule o ypes (c)-( ).
2.1 Bi-s able Ca aly ic P Sys ems wi h Ac i e Memb anes
Wi hou Pola iza ions, as Gene a ing De ices
As a gene a ing de ice, he esul (ou pu ) o a hal ing configu a ion o a bi-
s able ca aly ic P sys em is he ca dinali y o he mul ise associa ed wi h he
en i onmen in he las configu a ion. In hese P sys ems a non hal ing compu-
a ion yields no ou pu .
Defini ion 2. We deno e by N(Π) he se o all ou pu s o hal ing compu a ions
wi h espec o a bi-s able ca aly ic P sys em Π.
Theo em 1. Res ic ed bi-s able ca aly ic P sys ems wi h ac i e memb anes
wi hou pola iza ion, using ules o ype (b) and (d), a e compu a ionally com-
ple e.
P oo . Le Lbe a ecu si ely enume able language. Le Gbe a ma ix g amma
wi h appea ance checking such ha L(G)=L. We can conside ha G=
(N,{a},S,M,F) is gi en in Z-bina y no mal o m, in he s anda d no a ion.
Tha is,
•N=N1∪N2∪{S, Z, },wi h hese h ee se s mu ually disjoin .
•The ma ices in Ma e in one o he ollowing o ms:
1. (S→XA),whe e X∈N1,A∈N2,
2. (X→Y,A →x),whe e X, Y ∈N1,A∈N2,x∈(N2∪T)∗,|x|≤2,
3. (X→Y,A →),whe e X∈N1,Y ∈N1∪{Z},A∈N2,
4. (Z→λ).
•F={A→|∃m∈M(m=(X→Y,A →)}.
Mo eo e , i he special symbol Zappea s in a sen en ial o m w, hen we
ha e w=Zw, wi h w∈(T∪{})∗( ha is, no non e minal om N2is
p esen ).
•The ma ices in Mwill be o de ed as ollows:
m0:(S→Xini Aini ),wi h Xini ∈N1,A
ini ∈N2,
m1:
.
.
.
mk:
⎫
⎪
⎬
⎪
⎭
(X→α, A →x),wi h x∈N1,α∈N1∪{λ},A∈N2,
mk+1 :
.
.
.
mn:
⎫
⎪
⎬
⎪
⎭
(X→Y,A →).
(X→Z, A →),wi h X,Y ∈N1,A∈N2
mn+1 :(Z→λ)
We cons uc he sys em
Π=(Γ,K,{1},[]
1,M1,R),
whe e:
•Γ=N∪K∪{a, }∪{X,X,X|X∈N1},
•K={ci, ci|0≤i≤n},
•M
1={Xini ,A
ini ,E,c
0,c
1,...,c
n},
•The se Rconsis s o he ollowing ules:
(1.)
[ciX→ciY]1
[ciA→cix]1
[ciE→ci]1
[c0Y→c0Y]1
[c0Y→c0Y]1
⎫
⎪
⎪
⎪
⎪
⎬
⎪
⎪
⎪
⎪
⎭
o each mi:(X→Y,A →x),wi h 1 ≤i≤k.
These ules simula e he ma ices mi, o i=1,...,k. When we ha e in
he skin egion a mul ise con aining Xand he e exis s in Ma ma ix
mi:(X→Y,A →x), he ule [ ciX→ciY]1is applicable. In o de o
simula e he second componen o he g amma one o he ules [ c0Y→
c0Y]1,[c0Y→c0Y]1(ei he c0o c0is p esen , hence one o hese
ules can be used) p o ides a s ep in which i he e exis s an objec Ain
he skin egion, hen he ule [ ciA→cix]1can be applied; o he wise, i
he e is no such objec , he ule [ ciE→ci]1p oduces he ap symbol
showing ha we can no apply his ma ix and so his is no a co ec
de i a ion.
(2.)
[ciX→ciY]1
[c0Y→c0Y]1
[c0Y→c0Y]1
[ciA→ci]1
[ciY→ciY]1
⎫
⎪
⎪
⎪
⎪
⎪
⎬
⎪
⎪
⎪
⎪
⎪
⎭
o each mi:(X→Y,A →),wi h k+1≤i≤n
These ules simula e he ma ices mi, o i=k+1,...,n. When we
ha e in he skin egion a mul ise con aining Xand he e exis s in M
a ma ix mi:(X→Y,A →), he ule [ ciX→ciY]1is applicable.
In o de o simula e he second componen o he g amma , one o he
ules [ c0Y→c0Y]1,[ c0Y→c0Y]1p o ides a s ep in which i
he e exis s an objec Ain he skin egion, he ule [ ciA→ci]1is
applied; o he wise, i he e is no such objec , hen he ule [ ciY→ciY]1
comple es he simula ion o his ma ix.
(3.)
[a]1→a[]
1,[c0→c0]1,[c0→c0]1,
The fi s o hese wo las ules, [a]1→a[]
1, sends ou o he en-
i onmen he objec a. In a hal ing configu a ion o he sys em he
mul iplici y o he objec ain he en i onmen ep esen s he leng h o
he wo d gene a ed by G. I he compu a ion o he sys em simula es a
non e minal de i a ion in G, hen he ules [ c0→c0]1,[c0→c0]1
p oduce a non hal ing compu a ion.
F om he abo e ema ks i is easy o p o e ha he equali y leng h(L(G)) =
N(Π) holds, whe e leng h(L(G)) is he leng h se o he language L(G), ha is,
leng h(L(G)) = {|u||u∈L(G)}.
In he p e ious p oo we do no ac ually use he ac ha he memb anes
a e ac i e ( o ins ance, we do no use memb ane di ision); o he wise s a ed, he
p oo can be easily e o mula ed in e ms o basic ansi ion P sys ems, and his
makes necessa y he compa ison o Theo em 1 wi h uni e sali y esul s known
o such sys ems. Fi s , he uni e sali y is known o sys ems wi h bi-s able
ca alys s al eady om [5], whe e, howe e , one uses wo memb anes (see also
Theo em 3.4.7 om [2]; ou esul s imp o es on his poin , because we use only
one memb ane. Then, in [1] i is p o en ha wo ca alys s a e sufficien o ge
uni e sali y in P sys ems wi hou pola iza ions and wi hou p io i ies, bu he
sys ems conside ed in [1] con ain bo h ca aly ic and non-ca aly ic ules.
2.2 Recognize Bi-s able Ca aly ic P Sys ems wi h Ac i e
Memb anes Wi hou Pola iza ion
Defini ion 3. AP sys em wi h inpu is a uple (Π, Σ,iΠ), whe e ΠisaP
sys em, wi h wo king alphabe Γ, wi h pmemb anes labelled 1,...,p, and ini ial
mul ise s M1,...,Mpassocia ed wi h hem, Σis an (inpu ) alphabe s ic ly
con ained in Γ, he ini ial mul ise s a e o e Γ−Σ, and iΠis he label o a
dis inguished (inpu ) memb ane.
The compu a ions o a P sys em wi h an inpu in he o m o a mul ise m
o e Σa e defined in a na u al way; hey s a om a configu a ion which is
ob ained by adding he mul ise m o he ini ial configu a ion o he sys em.
Defini ion 4. Le (Π,Σ, iΠ)be a P sys em wi h inpu . Le Γbe he wo king
alphabe o Π,µ he memb ane s uc u e and M1,...,Mp he ini ial mul ise s

o Π.Le mbe a mul ise o e Σ. The ini ial configu a ion o (Π,Σ,iΠ) wi h
inpu mis (µ, M1,...,MiΠ∪m,...Mp).
In he case o P sys ems wi h inpu and wi h ex e nal ou pu , he concep
o compu a ion is in oduced in a simila way as o s anda d P sys ems – see
[2] – bu wi h a small change. We conside ha i is no possible o obse e he
in e nal p ocesses inside he P sys em and we can only know i he compu a ion
has hal ed ia some dis inguished objec s sen ou o he skin. We can o malize
hese ideas in he ollowing way.
Defini ion 5. A ecognize bi-s able ca aly ic P sys em is a P sys em wi h
inpu , (Π,Σ,iΠ), and wi h ex e nal ou pu such ha :
1. Πis a bi-s able ca aly ic P sys em.
2. The wo king alphabe o Πcon ains wo dis inguished objec s YES, NO.
3. All i s compu a ions hal .
4. I Cis a compu a ion o Π, hen ei he he objec YES o he objec NO
(bu no bo h) is sen o he en i onmen , and only in he las s ep o he
compu a ion.
We say ha Cis an accep ing compu a ion ( espec i ely, ejec ing compu-
a ion) i he objec YES ( espec i ely, NO) appea s in he en i onmen in he
hal ing configu a ion o C.
In wha ollows we will deal wi h ecognize bi-s able P sys ems wi h ac-
i e memb anes wi hou pola iza ions. Le us deno e by BAM he class o his
a ian o ecognize P sys ems.
3 The Complexi y Class PMCF
The fi s esul s abou “sol abili y” o NP–comple e p oblems in polynomial
ime (e en linea ) by cellula compu ing sys ems wi h memb anes we e ob ained
using a ian s o P sys ems ha lack an inpu memb ane. Thus, he cons uc i e
p oo s o such esul s need o design one sys em o each ins ance o he p oblem.
This d awback can be easily a oided i we conside a P sys em wi h inpu .
Then, he same sys em could sol e diffe en ins ances o he p oblem, p o ided
ha he co esponding inpu mul ise s a e in oduced in he inpu memb ane.
Ins ead o looking o a single sys em ha sol es a p oblem, we p e e de-
signing a amily o P sys ems such ha each elemen decides all he ins ances o
“equi alen size” o he p oblem.
Defini ion 6. Le Fbe a class o ecognize P sys ems. We say ha a deci-
sion p oblem X=(IX,θ
X)is sol able in polynomial ime by a amily Π=
(Π(n))n∈N+, o sys ems om F, and we deno e his by X∈PMCF,i he
ollowing is ue:
•The amily Πis polynomially uni o m by Tu ing machines; ha is, he e
exis s a de e minis ic Tu ing machine cons uc ing Π(n) om n∈N+in
polynomial ime.
•The e exis s a pai (g,h)o polynomial- ime compu able unc ions g:L→
n∈N+IΠ(n)and h:L→N+such ha o e e y u∈Lwe ha e
g(u)∈IΠ(h(u)), and
− he amily Πis polynomially bounded wi h ega d o (X, g, h); ha is,
he e exis s a polynomial unc ion p, such ha o each u∈IXe e y
compu a ion o Π(h(u)) wi h inpu g(u)is hal ing and, mo eo e , i pe -
o ms a mos p(|u|)s eps;
− he amily Πis sound wi h ega d o (X,g,h); ha is, o each u∈IX,i
he e exis s an accep ing compu a ion o Π(h(u)) wi h inpu g(u), hen
θX(u)=1;
− he amily Πis comple e wi h ega d o (X, g,h); ha is, o each u∈IX,
i θX(u)=1, hen e e y compu a ion o Π(h(u)) wi h inpu g(u)is an
accep ing one.
In he abo e defini ion we ha e imposed o e e y P sys em Π(n) obeconfluen ,
in he ollowing sense: e e y compu a ion wi h he same inpu p oduces he same
ou pu .
The class PMCFis closed unde polynomial– ime educ ion and comple-
men , as p o en, o ins ance, in [10].
4 Sol ing SAT in Linea Time
The SAT p oblem is he ollowing one: Gi en a boolean o mula in conjunc i e
no mal o m (CNF), o de e mine whe he o no i is sa isfiable; ha is, whe he
he e exi s an assignmen o i s a iables on which i e alua es ue.
We will add ess he esolu ion o his p oblem ia a b u e o ce algo i hm
wi hin he amewo k o ecognize bi-s able ca aly ic P sys ems wi h ac i e
memb anes wi hou cha ges. Ou s a egy will consis in:
•Gene a ion s age: Using memb ane di ision we gene a e all possible assign-
men s associa ed wi h he o mula.
•E alua ion s age: In each memb ane we e alua e he o mula on he assign-
men p oduced in ha memb ane.
•Checking s age: In each memb ane we check we he o no he o mula e al-
ua es ue on he assignmen om ha memb ane.
•Ou pu s age: Send o he en i onmen he igh answe acco ding o he
p e ious s age.
Le us conside he unc ion ,defined by n, m=((n+m)(n+m+1)/2)+n
o ϕ=C1∧···∧Cma p oposi ional o mula in CNF and Va (ϕ)={x1,...,x
n}.
The unc ion ,is polynomial- ime compu able (i is p imi i e ecu si e and
bijec i e om N2on o N). Also, he in e se unc ion o ,is polynomial.
The amily p esen ed he e is
Π={(Π(n, m),Σ(n, m),i(n, m)) |(n, m)∈N2}.
Fo each elemen o he amily, he inpu alphabe is
Σ(n, m)={xi,j, xi,j |1≤i≤m, 1≤j≤n},
he inpu memb ane is i(n, m) = 2, and he P sys em
Π(n, m)=(Γ(n, m),K(n, m),{1,2},µ,M1,M2,R)
is defined as ollows:
•Bi-s able ca alys s:
K(n, m)={ j, j,
j, j,s
i, si, ans, ans |1≤i≤m, 1≤j≤n}.
•Wo king alphabe :
Γ(n, m)=Σ(n, m)∪K(n, m)∪{ j,p
j,n
j|1≤j≤n}
∪{ci,
i|1≤i≤m}∪{nok|1≤k≤n+m+3}
∪{, yes, Y ES, NO}.
•Memb ane s uc u e: µ=[
1[2]2]1(we will say ha e e y memb ane wi h
label2isanin e nal memb ane).
•Ini ial Mul ise s:
M1={no1, ans},
M2={ 1,...,
n, 1,..., n, 1,..., n, s1,...,sm,c
1}.
•The se Rconsis s o he ollowing ules:
1. [ j]2→[pj]2[nj]2,1≤j≤n.
The goal o hese ules is o gene a e an in e nal memb ane o each
assignmen o he a iables o he o mula. The new memb ane whe e
he objec pjappea s ep esen s he assignmen whe e xj= ue and he
new memb ane whe e he objec njappea s ep esen s he assignmen
whe e xj= alse.
2. [ jpj→ jpj]2
[ jxij → j i]2
[ jxij → j]2
⎫
⎬
⎭
o 1 ≤i≤m, 1≤j≤n.
The objec pjac i a es he ca alys jwhich “e ases” he objec s xi,j
( hese objec s ep esen he li e als ¬xj), bu eac s wi h he objec s
xi,j ( hese objec s ep esen he li e als xj) o p oduce he objec i
( his objec indica es ha he clause numbe ie alua es ue on he
assignmen associa ed wi h he memb ane).
3.
[ jnj→ jnj]2
[ jxij → j i]2
[ jxij → j]2
⎫
⎬
⎭
o 1 ≤i≤m, 1≤j≤n.
The objec njac i a es he ca alys jwhich “e ases” he objec s xi,j
( hese objec s ep esen he li e als xj), bu eac s wi h he objec s xi,j
( hese objec s ep esen he li e als ¬xj) o p oduce he objec i( his
objec indica es ha he clause numbe ie alua es ue on he assign-
men associa ed wi h he memb ane).
4. [ si i→si i]2, o 1 ≤i≤m,
[sici→sici+1 ]2, o 1 ≤i≤m−1,
[smcm→smyes ]2.
The objec s cia e coun e s which ep esen he numbe o clauses ha
e alua e ue on he assignmen associa ed wi h he in e nal memb ane.
So he objec ci, o 1 ≤i≤m−1, eac s wi h he ca alys si, which is
ac i a ed by he objec i, o p oduce he objec ci+1, and he objec cm
eac s wi h he objec m o p oduce he objec yes in o de o show ha
e e y clause o he o mula e alua es ue on he assignmen associa ed
wi h he in e nal memb ane.
5. [ yes ]2→yes []
2,
[ans yes →ansY ES ]1,
[YES]1→YES[]
1.
These ules p oduce and send he objec YES o he en i onmen .
6. [ noi→noi+1 ]1, o 1 ≤i≤n+2m+3,
[ans non+2m+4 →ansNO ]1,
[NO ]1→NO []
1.
These ules p oduce and send ou he objec NO o he en i onmen .
No e ha he objec NO appea s one s ep la e han he objec YES
and ha he ca alys ans ge ba ed in he ou pu s age in o de o make
su e ha he sys em sends ou he igh answe .
5 An O e iew o he Compu a ion
Fi s o all we mus define a sui able pai (g,h) o polynomial- ime compu able
unc ions (see Defini ion 6) associa ed wi h he SAT p oblem. Gi en a o mula
ϕ=C1∧...C
min CNF such ha Va (ϕ)={x1,...,x
n}, we define h(ϕ)=
n, m( ecall he bijec ion men ioned in he p e ious sec ion) and g(ϕ)={xij |
xj∈Ci}∪{xj|¬xj∈Ci}
Nex we will in o mally desc ibe how he ecognize bi-s able ca aly ic P
sys em Π(h(ϕ)) wi h inpu g(ϕ) wo ks.
The compu a ion s a s wi h he gene a ion and e alua ion s ages. These wo
s ages ake place in pa allel ollowing he ules om g oup 1 o 3. The gene -
a ion o memb anes is con olled by he objec s j, o 1 ≤j≤n. When an
objec jis p esen in an in e nal memb ane he ule in 1 is applicable and
so he sys em p oduces wo new memb anes. In one o hese wo new mem-
b anes he objec pjappea s encoding ha in he assignmen associa ed wi h
ha his a ian is compu a ionally comple e and able o sol e efficien ly NP-
comple e p oblems like SAT.
Fu u e p ojec s a e o design amilies o ecognize bi-s able ca aly ic P sys-
ems o sol e nume ical NP-comple e p oblems like Knapsack and T ipa i e
Ma ching and o s udy he compu a ional powe and efficiency o P sys ems
wi h ac i e memb anes wi hou pola iza ions.
CLIPS has been shown o be a con enien p og amming language o simu-
la ing P sys ems and i was help ul o debug he design and o unde s and how
he P sys ems om he amily Πwo k.
Acknowledgemen
This wo k is suppo ed by he Minis e io de Ciencia y Tecnolog´ıa o Spain, by
he Plan Nacional de I+D+I (2000–2003) (TIC2002-04220-C03-01), cofinanced
by FEDER unds, and by a FPI ellowship (o he second au ho ) om he
Uni e si y o Se ille.
Re e ences
1. R. F eund, L. Ka i, M. Oswald, P. Sosik, Compu a ionally uni e sal P sys ems
wi hou p io i ies: Two ca alys s suffice. Theo e ical Compu e Sci., o appea .
2. Gh. P˘aun, Memb ane Compu ing. An In oduc ion, Sp inge -Ve lag, 2002.
3. Gh. P˘aun, Compu ing wi h memb anes. Jou nal o compu e and Sys ems Sciences,
61(1), 2000, 108–143.
4. Gh. P˘aun, M.J. P´e ez-Jim´enez, A. Riscos-N´u˜nez, P sys ems wi h ables o ules.
In: Gh. P˘aun, A. RiscosN´u˜nez, A. Rome o-Jim´enez, F. Sancho-Capa ini, eds.,
P oceedings o he Second B ains o ming Week on Memb ane Compu ing, Repo
RGNC 01/04, 2004, 366–380.
5. Gh. P˘aun, S. Yu, On synch oniza ion in P sys ems. Fundamen a In o ma icae, 38,
4 (1999), 397–410.
6. M.J. P´e ez-Jim´enez, A. Rome o-Jim´enez, F. Sancho-Capa ini, Teo ´ıa de la Com-
plejidad en modelos de compu acion celula con memb anas, Ed. K onos, Se illa,
2002.
7. M.J. P´e ez-Jim´enez, A. Riscos-N´u˜nez, Sol ing he Subse -Sum p oblem by ac i e
memb anes. New Gene a ion Compu ing, in p ess.
8. M.J. P´e ez-Jim´enez, A. Riscos-N´u˜nez, A linea - ime solu ion o he Knapsack
p oblem using ac i e memb anes. Lec u e No es in Compu e Science, 2933 (2004)
140–152.
9. M.J. P´e ez-Jim´enez, F.J. Rome o-Campe o, A CLIPS simula o o ecognize
P sys ems wi h ac i e memb anes. In: Gh. P˘aun, A. Riscos-N´u˜nez, A. Rome o-
Jim´enez, F. Sancho-Capa ini, eds., P oceedings o he Second B ains o ming Week
on Memb ane Compu ing, Repo RGNC 01/04, 2004, 387–413.
10. M.J. P´e ez-Jim´enez, A. Rome o-Jim´enez, F. Sancho-Capa ini, A polynomial com-
plexi y class in P sys ems using memb ane di ision. In: E. Csuhaj-Va j´u, C. Kin-
ala, D. Wo schke, Gy. Vaszyl, eds., P oceedings o he Fi h In e na ional Wo k-
shop on Desc ip ional Complexi y o Fo mal Sys ems, 2003, 284–294.