Sol ing he BINPACKING P oblem
by Recognize P Sys ems wi h Ac i e Memb anes
Ma io J. P´
EREZ-JIM´
ENEZ, F ancisco Jos´e ROMERO-CAMPERO
Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A i icial In elligence
Uni e si y o Se illa
A da. Reina Me cedes s/n, 41012 Se illa, Spain
E-mail: {Ma io.Pe ez, F ancisco-Jose.Rome o}@cs.us.es
Abs ac . In his pape we p esen an e ec i e solu ion o he BINPACKING
p oblem using a amily o ecognize P sys ems wi h ac i e memb anes, inpu
memb ane and ex e nal ou pu . The analysis o he solu ion p esen ed he e
will be done o m he poin o iew o complexi y classes.
1 In oduc ion
P sys ems a e an eme gen b anch in he ield o Na u al Compu ing. This uncon en ional
model o compu a ion is p esen ed as a kind o dis ibu ed pa allel compu ing model and i
is based upon he obse a ion ha he p ocesses which ake place in he complex s uc u e
o a li ing cell can be conside ed as compu a ions.
Since Gh. P˘aun in oduced i in [2] se e al a ian s ha e been conside ed om di e en
app oaches. A ai ly comple e compendium abou P sys ems can be ound in [3]. Many o
he p oposed a ian s ha e been p o ed o be compu a ional comple e, hei compu a ional
powe is ha o Tu ing machines; besides some a ian s o P sys ems ha e been p o ed
o be compu a ional e icien , hey ha e been shown o be able o sol e NP-comple e
p oblems in polynomial ime (see [3] Chap e 7).
The solu ion p esen ed he e has been designed h ough a amily o ecognize P sys ems
wi h ac i e memb anes, inpu memb ane and ex e nal ou pu . In pa icula , P sys ems
wi h ac i e memb anes a e s udied in [3], sec ion 7.2. We ha e ollowed he ideas and
schemes used o sol e o he s nume ical NP-p oblems as he Subse –Sum in [9] and he
Knapsack p oblem in [10]. Due o he s ong simila i ies o he design o hese solu ions
he idea o a cellula p og amming language seems possible as i is sugges ed in [12].
The analysis o he p esen ed solu ion will be done om he poin o iew o he com-
plexi y classes. A complexi y class o a model o compu a ion is a collec ion o p oblems
ha can be sol ed (o languages ha can be decided) by some de ices o his model wi h
simila compu a ional esou ces. We will s udy he complexi y o he p oposed solu ion
wi hin he amewo k o he complexi y classes in P sys ems s udied in [7] and [8].
The pape is o ganized as ollows: Sec ion 2 ecalls ecognize P sys ems wi h ac i e
memb anes, inpu memb ane and ex e nal ou pu . In sec ion 3 he complexi y classes
o P sys ems a e b ie ly in oduced. Sec ions 4, 5 and 6 show a cellula solu ion o he
414
BINPACKING p oblem. In sec ion 7 we use a CLIPS simula o o ecognize P sys ems
wi h aci e memb anes o show a session o he BINPACKING p oblem. Conclusions a e
gi en in sec ion 8.
2 Recognize P sys ems wi h Ac i e Memb anes, Inpu
Memb ane and Ex e nal Ou pu
De ini ion 2.1 A decision p oblem, X, is a pai (IX, θX)such ha IXis a language o e
a ini e alphabe (whose elemen s a e called ins ances) and θXis a o al boolean unc ion
o e IX.
De ini ion 2.2 AP sys em wi h inpu is a uple (Π,Σ, iΠ), whe e:
•Πis a P sys em, wi h wo king alphabe Γ, wi h pmemb anes labelled by 1, . . . , p, and
ini ial mul ise s M1, . . . , Mpassocia ed wi h hem.
•Σis an (inpu ) alphabe s ic ly con ained in Γ.
•The ini ial mul ise s a e o e Γ−Σ.
•iΠis he label o a dis inguished (inpu ) memb ane.
De ini ion 2.3 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 con igu a ion o (Π,Σ, iΠ) wi h inpu mis (µ0, M0), whe e
µ0=µ,M0(j) = Mj, o each j6=iΠ, and M0(iΠ) = MiΠ∪m.
The compu a ions o a P sys em wi h inpu m∈M(Σ), a mul ise o e Σ, a e de ined
in a na u al way. The only no el y is ha he ini ial con igu a ion mus be he ini ial
con igu a ion o he sys em associa ed wi h he inpu mul ise m∈M(Σ).
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 bu wi h a sligh a ian . In he con igu a ions, we will
no wo k di ec ly wi h he memb ane s uc u e µbu wi h ano he s uc u e associa ed
wi h i including, in some sense, he en i onmen .
De ini ion 2.4 Le µ= (V(µ), E(µ)) be a memb ane s uc u e. The memb ane s uc u e
wi h ex e nal en i onmen associa ed wi h µis he oo ed ee Ex (µ)such ha : (a) he
oo o he ee is a new node ha we will deno e en ;(b) he se o nodes is V(µ)∪
©en ª; and (c) he se o edges is E(µ)∪©{en , skin}ª. The node en is called ex e nal
en i onmen o he s uc u e µ.
No e ha we ha e only included a new node ep esen ing he en i onmen which is
only connec ed wi h he skin, while he o iginal memb ane s uc u e emains unchanged.
In his way, e e y con igu a ion o he sys em in o ms abou he con en s o he ex e nal
en i onmen .
De ini ion 2.5 A ecognize P sys em is a P sys em wi h inpu , (Π,Σ, iΠ), and wi h
ex e nal ou pu such ha :
1. The wo king alphabe con ains wo dis inguished elemen s YES, NO.
415
2. All i s compu a ions hal .
3. I Cis a compu a ion o Π, hen ei he some objec YES o some objec N0 (bu no
bo h) mush ha e been eleased in 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 com-
pu a ion) i he objec YES ( espec i ely, N0) appea s in he ex e nal en i onmen
associa ed o he co esponding hal ing con igu a ion o C.
This ecognize sys ems a e specially sui able when ying o sol e decision p oblems.
In his pape we will deal wi h ecognize P-Sys ems wi h Ac i e Memb anes, Inpu
Memb ane and Ex e nal Ou pu . Le ’s emembe ha a P sys em wi h Ac i e Memb anes
is a uple:
Π = (Σ, H, µ, ω1, . . . , ωm, R)
whe e:
1. m≥1, is he ini ial deg ee o he sys em;
2. Σ is he alphabe o symbol-objec s;
3. His a ini e se o labels o memb anes;
4. µis a memb ane s uc u e, o mmemb anes, labelled (no necessa ily in a one- o-one
manne ) wi h elemen s o H;
5. ω1, . . . , ωma e s ings o e Σ, desc ibing he ini ial mul ise s o objec s placed in he
m egions o µ;
6. Ris a ini e se o e olu ion ules, o he ollowing o ms:
(a) [ a→ω]α
h o h∈H,α∈ {+,−,0},a∈Σ, ω∈Σ∗,objec e olu ion ules: This
is an objec e olu ion ule, associa ed wi h a memb ane labelled wi h hand
depending on he pola i y o ha memb ane, bu no di ec ly in ol ing he
memb ane.
(b) a[ ]α1
h→[b]α2
h o h∈H,α1, α2∈ {+,−,0},a, b ∈Σ, communica ion ules
(send in ules): An objec om he egion immedia ely ou side a memb ane la-
belled wi h his in oduced in his memb ane, possibly ans o med in o ano he
objec , and simul aneously, he pola i y o he memb ane can be changed.
(c) [ a]α1
h→b[ ]α2
h o h∈H,α1, α2∈ {+,−,0},a, b ∈Σ, communica ion
ules (send ou 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 , and
simul aneously, he pola i y o he memb ane can be changed.
(d) [ a]α
h→b o h∈H,α∈ {+,−,0},a, b ∈Σ, dissol ing ules: A memb ane
labelled wi h his dissol ed in eac ion wi h an objec . The skin is ne e dis-
sol ed.
(e) [ a]α1
h→[b]α2
h[c]α3
h o h∈H,α1, α2, α3∈ {+,−,0},a, b, c ∈Σ, di ision ules
o elemen 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 and hei
pola i ies.
416
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), hen we suppose ha
i s he e olu ion ules o ype (a) 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 (b)-(e).
Le us deno e by AM he class o language ecognize P sys ems wi h ac i e memb anes
using 2-di ision (see [3], sec ion 7.2).
3 The complexi y class PMCF
Roughly speaking, a compu a ional complexi y s udy o a solu ion o a p oblem is an
es ima ion o he esou ces ( ime, space, ...) ha a e equi ed h ough all he p ocesses
ha ake place in he way om he ba e ins ance o he p oblem up o he inal answe .
The i 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.
I we wan ed o pe o m such a solu ion o some decision p oblem in a labo a o y, we
will ind a d awback on his app oach: a sys em cons uc ed o sol e a conc e e ins ance is
useless when ying o sol e ano he ins ance. This handicap can be easily o e aken i we
conside a P sys em wi h inpu . Then, he same sys em could sol e di e 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 designing a
amily o P sys ems such ha each elemen decides all he ins ances o ”equi alen size”,
in ce ain sense.
Le us now in oduce some basic concep s be o e he de ini ion o he complexi y class
i sel .
De ini ion 3.1 Le Lbe a language, Fa class o P sys ems wi h inpu and Π=
(Π(n))n∈N+a amily o P sys ems o F. A polynomial encoding o Lin Πis 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)).
417
Lemma 3.1 Le L1⊆Σ1and L2⊆Σ2be languages. Le Fbe a class o P sys ems
wi h inpu and Π= (Π(n))n∈N+a amily o P sys ems o F. I : Σ1→Σ2is a
polynomial ime educ ion om L1 o L2, and (g, h)is a polynomial encoding o L2in Π,
hen (g◦ , h ◦ )is a polynomial encoding o L1in Π.
De ini ion 3.2 Le Fbe a class o ecognize P sys ems, :N+→N+a
o al ecu si e unc ion, and X= (IX, θX)a decision p oblem. We say ha
X∈MCF( )i he e exis s a amily, Π= (Π(n))n∈N+, o P sys ems such ha :
•Πis F–consis en : ∀n∈N+,Π(n)∈ F.
•Πis uni o m: he e exis s a de e minis ic Tu ing machine ha om n∈N+con-
s uc s Π(n)in polynomial ime.
•The e exis s a polynomial encoding (g, h) om IX o Π e i ying:
– Π is –bounded, ega ding o (g, h).
Fo each u∈IX, all compu a ions o Π(h(u)) wi h inpu g(u)hal in, a mos ,
(|u|)s eps.
– Π is X–sounded, ega ding o (g, h).
Fo each u∈IX, i e e y compu a ion o Π(h(u)) wi h inpu g(u)is an accep ing
compu a ion, hen θX(u) = 1.
– Π is X–comple e, ega ding o (g, h).
Fo 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 compu a ion.
Rema k 3.1 In he abo e de ini ion we ha e imposed e e y P sys em Π(n) o be con luen ,
in he ollowing sense: o e e y inpu m, ei he e e y compu a ion o Π(n)wi h inpu
mis an accep ing compu a ion, o e e y compu a ion o Π(n)wi h inpu mis a ejec ing
compu a ion.
De ini ion 3.3 The polynomial complexi y class associa ed wi h a collec ion o ecognize
P sys ems, F, is de ined as ollows:
PMCF=[
polynomial
MCF( )
P oposi ion 3.1 Le Fbe a class o P sys ems wi h inpu . Le X, Y be p oblems such
ha Xis educible o Yin polynomial ime. I Y∈PMCF, hen X∈PMCF.
4 The BINPACKING P oblem
The BINPACKING p oblem can be s a ed as ollows:
Gi en a se A={s1, . . . , sn}, a weigh unc ion ω:A→Nand wo cons an s
b∈N,c∈Ndecide whe he o no he e exis s a pa i ion o Ain o bsubse s
such ha hei weigh s do no exceed c.
418

This p oblem can be seen as he si ua ion when we ha e ni ems, bbins o capaci y c
and we ha e o in oduce he i ems in he bins.
We will ep esen he ins ances o he p oblem using uples o he kind
(n, (ω1, . . . , ωn), b, c), whe e nis he numbe o i ems, (ω1, . . . , ωn) a e he weigh s, bis he
numbe o bins and c hei capaci y.
We will ace he esolu ion o his p oblem ia a b u e o ce algo i hm, in he amewo k
o ecognize P sys ems wi h ac i e memb anes using 2-di ision, wi hou coope a ion no
p io i y among ules. Ou s a egy will consis in:
•Fo each bin:
–Gene a ion s age: Memb ane di ision is used un il a speci ic memb ane o each
subse So he emaining i ems is ob ained.
–Calcula ion s age: In each memb ane he weigh o he associa ed subse is
calcula ed.
–Checking s age : The condi ion ω(S)≤cis checked o e e y subse S⊆A.
–T ansi ion s age: I he associa ed subse sa is ies ω(S)≤c hen we in oduce
hese i ems in his bin and we epea he p ocess wi h he emaining i ems and
bins; o he wise he memb ane is dissol ed.
•Ou pu s age: The answe is eleased in o he en i onmen acco ding o he esul s
in he checking s age o each bin.
Now we cons uc a amily o ecognize P sys ems wi h ac i e memb anes using 2-
di ision sol ing he BINPACKING p oblem.
Le us conside a polynomial bijec ion, h i, be ween N3and N(e.g. hx, y, zi=
hhx, yi, zi, induced by he pai unc ion hx, yi= (x+y)·(x+y+ 1)/2 + x).
The amily p esen ed he e is
Π={(Π(hn, b, ci),Σ(n, b, c), i(n, b, c)) : (n, b, c)∈N3}
Fo each elemen o he amily, he inpu alphabe is Σ(n, b, c) = {s1, . . . , sn, z1, . . . , zn},
he inpu memb ane is i(n, b, c) = 2, and he P sys em Π(hn, b, ci) =
(Γ(n, b, c),{1,2}, µ, M1,M2, R) is de ined as ollows:
•Wo king alphabe :
Γ(n, b, c) = {zijk, sijk, Zijk, Sijk, z0, z, w, W, gl, T, m, D, D, ˆ
D, G, G1, , neg, de,
Y ES, NO : 1 ≤i≤b, −1≤j≤n, 1≤k≤n, 0≤l≤2n+ 1,0≤m≤2n+ 1}
•Memb ane s uc u e: µ= [1[2]2]1
•Ini ial Mul ise s: M1={ 1},M2={ 1, g0, Dc}
•The se o e olu ion ules, R, consis s o he ollowing ules:
1. [ sk→s1, k, k ]0
2; [ zk→z1, k, k ]0
2,1≤k≤n
These ules ini ialize he algo i hm. The objec s o ype sand zwill ha e h ee
subindixes. The i s one, 1 ≤i≤b, will ep esen he numbe o he bin whe e
he i em ep esen ed by his objec can be added. The second one, −1≤j≤n
419
will deno e i s posi ion in he s ack o be added in he cu en bin; i second
subindixe is -1 hen his i em has no been chosen o be added in he bin. The
hi d one, 1 ≤k≤nwill be use o show o which i em his objec is used o
ep esen i s weigh .
2. [ zi, 1, k ]0
2→[z]+
2[zi, −1, k ]0
2,1≤k≤n , 1≤i≤b−1
The goal o hese ules is o gene a e one memb ane o each subse o he
emaining i ems ha can be added in he cu en bin. When he objec zi, 1, k
is p esen in a neu ally cha ged memb ane wi h label 2 i means ha he
sys em has o decide whe he o no he i em numbe kis chosen o he subse
o be added in he bin numbe i.
So he memb ane is di ided in o wo memb anes: one posi i ely cha ged which
will ep esen he subse whe e he i em numbe kis chosen o be in oduced
in he bin, he objec zappea s in his memb ane; and he o he one will be
nega i ely cha ged and will ep esen he subse whe e he i em numbe kis
no added in he bin, so we se he second subindixe o −1, zi, −1, k.
3. [ si, 0, k →w]+
2,1≤k≤n, 1≤i≤b−1
The p esence o he objec s si, 0, k in a posi i ely cha ged memb ane wi h label
2 means ha he i em numbe kis added o he subse associa ed o he mem-
b ane. The mul iplici y o he objec s·,·, k encodes he weigh o he i em k
and he mul iplici y o he objec wencodes he weigh o he subse associa ed
o he memb ane.So when an i em is added o he subse associa ed o he
memb ane he objec s si, 0, k e ol e o w.
4. [ z]+
2→][ ]0
2
The elemen zis used o change he pola iza ion o he memb anes wi h label
2 om posi i e o neu al.
5. [ si, j, k →si, j−1, k]0
2; [ zi, j, k →zi, j−1, k]0
2; 0 ≤j≤n, 1≤k≤n, 1≤i≤
b−1
Once he i em analyze has been o no in oduced o he bin hese ules upda e
he s ack o i ems by o a ing he second subindixes o he objec s o ype s
and z.
6. [ gi→gi+1 ]0
2; [ gi→gi+1 ]+
2; 0 ≤i≤2n−1
The objec s gia e coun e s used in he gene a ion s age.
7. [ g2n→g2n+1 , 0]0
2; [ g2n→g2n+1 , 0]+
2;
The gene a ion s age akes 2ns eps. The objec g2nwill p oduce he objec s
g2n+1 and 0which will begin he p epa a ion o he checking s age.
8. [ g2n+1 ]0
2→][ ]−
2;
The i em g2n+1 will change he pola iza ion o he memb anes wi h label 2 om
neu al o nega i e.
9. [ w→W]−
2
In he p epa a ion o he checking s age he objec s wa e enamed o Win
o de o a oid con lic s wi h he p e ious s age.
10. [ si, −1, k →Si, k, k ]−
2; [ zi, −1, k →Zi, k, k ]−
2; 1 ≤i≤b−1,1≤k≤n
The objec s si, −1, k and zi, −1, k a e enamed o Si, −1, k and Zi, −1, k be o e he
checking s age in o de o a oid con lic s wi h he p e ious s age.
420
11. [ D→D , ˆ
D]−
2
The mul iplici y o he objec s D ep esen s he capaci y o he bins. In he
checking s age we ha e o check i he weigh o he subse in oduced in he
cu en bin exceeds o no i s capaci y. A he beginning o his s age he
objec s Dp oduce he objec s Dand ˆ
D. The objec s ˆ
Dwill be used in he
checking s age o he cu en bin and he objec s Dwill keep he capaci y o
he bins so his in o ma ion can be used la e in he compu a ion.
12. [ ˆ
D]−
2→][ ]0
2; [ W]0
2→][ ]−
2
Wi h hese ules he sys em checks whe he o no he weigh o he subse
in oduced in he bin exceeds i s capaci y.
13. [ i→ i+1 ]−
2; [ j→ j+1 ]0
2; 0 ≤i≤2c−1,1≤j≤2c−1
The objec s ia e coun e s used in he checking s age.
14. [ 2c→ 2c+1, G, z0]−
2; [ 2c;→ 2c+1, G, z0]0
2;
The checking s age akes 2cs eps. The objec s 2cwill p oduce he objec s
2c+1, G and z0which will begin he ansi ion o he nex bin.
15. [ 2c+1 ]−
2→][ ]+
2; [ 2c+1 ]−
2→][ ]+
2;
The objec 2c+1 changes he pola iza ion o memb anes wi h label 2 om
nega i e o posi i e and he ansi ion s age begins.
16. [ W]+
2→]
I he e a e s ill objec s Wwhen he checking s age has inished i means ha
he mul iplici y o objec s Wexceeded he mul iplici y o objec s ˆ
D. So he
weigh o he subse in oduced in he bin exceeded i s capaci y, ha is his
is no a possible solu ion o he p oblem and he co esponding memb ane is
dissol ed.
17. [ ˆ
D→]]+
2
The emaining objec s ˆ
Da e ”e ased” in he ansi ion s age.
18. [ D→D]+
2
The objec s Da e enamed o Dso hey can be used in he compu a ion o
he nex bin.
19. [ Si, k, k →si+1, k, k ]+
2; [ Zi, k, k →zi+1, k, k ]+
2; 1 ≤i≤b−2; 1 ≤k≤n
The objec s Si, k, k and Zi, k, k a e enamed o si+1, k, k and zi+1, k, k so hey can
be used in he compu a ion o he nex bin.
20. [ G→G1]+
2; [ G1→g1]0
2
These ules p oduce he objec g1 ha will be used as coun e in he gene a ion
s age o he nex bin.
21. [ z0→z]+
2
The objec zis p oduced o inish he ansi ion s age.
22. [ Sb−1, k, k →w]+
2; [ Zb−1, k, k →]]+
2; 1 ≤k≤n
These ules in oduce all he emaining i ems in he las bin.
23. [ i→ i+1 ]0
2; [ i→ i+1 ]+
2; [ i→ i+1 ]−
2; 0 ≤i≤2nb + 2cb + 5b−2n−
2c−5
The objec s ia e coun e s ha will show when he checking s age o he las
bin mus begin.
421
24. [ 2nb+2cb+5b−2n−2c−4→neg, T, d0]+
2;
This ule will o ce he sys em o skip he gene a ing s age o he las bin and
will o ce he checking s age begin.
25. [ T→ 0]0
2; [ neg ]0
2→][ ]−
2
These ules ini ialize he checking s age o he las bin.
26. [ di→di+1]0
2,[di→di+1]−
2,[d2c+3 ]0
2→Y ES ; 0 ≤i≤2c+ 2
The objec s dia e coun e s in he memb anes wi h label 2 ha e en ually will
p oduce he answe YES.
27. [ di→di+1 ]0
1; [ d2nb+2cb+5b−2n+3 →NO ]0
1
The objec s dia e coun e s in he skin ha will e en ually p oduce he answe
NO.
28. [ Y ES ]0
1→Y ES[ ]+
1; [ NO ]0
1→Y ES[ ]−
1
These ules eleased he answe in o he en i onmen . No e ha i he answe
o he sys em mus be YES his objec will appea in he skin one s ep be o e
he objec NO so no con lic occu s.
5 An O e iew o he Compu a ion
Fi s o all we mus de ine a polynomial encoding o he Binpacking p oblem in he amily
Πin o de o s udy he complexi y o he p oblem wi h espec o i . Gi en an ins ance
u= (n, (ω1, . . . , ωn), b, c) o he Binpacking p oblem, we de ine h(u) = hn, b, ci( ecall he
bijec ion men ioned in he p e ious sec ion) and g(u) = {z1, . . . zn, sω1
1, . . . , sωn
n}. Now we
will in o mally desc ibe how he sys em Π(h(u)) wi h inpu g(u) wo ks.
In he i s s ep o he compu a ion, he ules [ sk→s1, k, k ]0
2; [ zk→z1, k, k ]0
2a e
applied o ini ialize he compu a ion. The i s subindixe o hese objec s ep esen s he
bin we a e dealing wi h.
Fo each bin i, o 1 ≤i≤b−1, he gene a ion and calcula ion s ages ake place in
pa allel, ollowing he ins uc ions om he ules in 1 - 7. This wo s ages end when he
objec g2n+1 se he pola iza ion o he memb ane o nega i e. We gene a e e e y subse
o he emaining i ems, associa ing each subse o a single wo king memb ane.
Le us in oduce he concep o subse associa ed wi h an in e nal memb ane h ough
he ollowing ecu si e de ini ion:
•The subse associa ed wi h he ini ial memb ane is he emp y one.
•When an objec zi, ·, k does no appea s in a inne memb ane i means ha he k- h
i em o Ahas been in oduced in he bin numbe i. In he o he hand when an
objec zi, −1, k appea s in an inne memb ane, i means ha he k- h i em o Ahas
been le ou o he bin numbe iand so i can be in oduced in he ollowing bins.
•When a di ision ule is applied, he wo newbo n memb anes inhe i he associa ed
subse o m he o iginal memb ane.
As we ha e men ioned abo e, he wo i s s ages a e ca ied ou in pa allel. Indeed,
he e is only a gap o one s ep o compu a ion be ween he momen when an i em is
added o he associa ed subse and he momen when he new weigh o he subse is
upda ed. Fo example, o he i em numbe 1 which is ep esen ed by he objec s s1and
422
Con igu a ion numbe : 25
[en i onmen [mul ise YES ,]]
[skin [child en ]
[label 1]
[pola i y +]
[mul ise , NO , YES , ]]
The sys em has eached a hal ing con igu a ion in he s ep numbe 25
and he elemen YES has been eleased in o he en i onmen .
8 Conclusions
In his pape we ha e p esen ed an e ec i e solu ion o he BINPACKING p oblem
h ough a amily o ecognize P sys ems wi h ac i e memb anes. This has been done in
he amewo k o complexi y classes in cellula compu ing wi h memb anes.
The design p esen ed he e is e y simila o he solu ions o nume ial NP-comple e
p oblems s udied in [9], [10] and [12]. The s ong simila i ies in hei designs show ha he
idea o a cellula p og amming language is posible, indica ing some “sub ou ines” ha can
be used in a a ie y o si ua ions and he e o e could be use ul o a acking new p oblems
in he u u e. As an example o he use ulness o he sub ou ines ou lined in [12], le us
see how he design o he solu ions o he BINPACKING would look like:
BINPACKING
o i=1, . . . , b-1 do
gen −subse s(ni)
calc −weigh (ni)
ename
check −weigh
ma ke −leq
coun e (n)
clean −dissol e
end o .
calc −weigh (nb)
ename
check −weigh
ma ke −leq
coun e (n)
clean −dissol e
de ec o
answe
The CLIPS simula o o P sys ems p esen ed in [11] is a e y use ul ool ha has
helped o debug he design and o unde s and be e 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 Tec-
nolog´ıa o Spain, by he Plan Nacional de I+D+I (2000–2003) (TIC2002-04220-C03-01),
429

co inanced 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] Co d´on-F anco, A., Gu i´e ez-Na anjo, M.A., P´e ez-Jim´enez, M.J., Sancho-
Capa ini, F.: A P olog simula o o de e minis ic P sys ems wi h ac i e memb anes,
New Gene a ion Compu ing, in p ess.
[2] P˘aun, Gh.: Compu ing wi h memb anes, Jou nal o Compu e and Sys ems Sciences,
61, 1 (2000), 108–143.
[3] P˘aun, Gh.: Memb ane Compu ing. An In oduc ion, Sp inge -Ve lag, 2002.
[4] P˘aun, Gh., Rozenbe g, G.: A guide o memb ane compu ing, Theo e ical Compu e
Sciences, 287 (2002), 73–100.
[5] P˘aun, Gh., Rozenbe g, G., Salomaa, A.: Memb ane compu ing wi h ex e nal ou pu ,
Fundamen a In o ma icae, 41, 3 (2000), 313–340.
[6] P´e ez-Jim´enez, M.J., Rome o-Jim´enez, A., Sancho-Capa ini, F.: Sol ing VALIDITY
p oblem by ac i e memb anes wi h inpu , P oceedings o he B ains o ming Week on
Memb ane Compu ing, M. Ca alie e, C. Ma in-Vide, and Gh. P˘aun (eds), Repo
GRLMC 26/03, 279–290.
[7] P´e ez-Jim´enez, M.J., Rome o-Jim´enez, A., Sancho-Capa ini, F.: Teo ´ıa de la Com-
plejidad en modelos de compu acion celula con memb anas, Edi o ial K onos, 2002.
[8] P´e ez-Jim´enez, M.J., Rome o-Jim´enez, A., Sancho-Capa ini, F.: A polynomial com-
plexi y class in P sys ems using memb ane di ision, P oceedings o he 5 h Wo kshop
on Desc ip ional Complexi y o Fo mal Sys ems, E. Csuhaj-Va j´u, C. Kin ala, D.
Wo schke, and Gy. Vaszyl (eds.), 2003, 284–294.
[9] P´e ez-Jim´enez, M.J., Riscos-N´u˜nez, A.: Sol ing he Subse -Sum p oblem by ac i e
memb anes, New Gene a ion Compu ing, in p ess.
[10] P´e ez-Jim´enez, M.J., Riscos-N´u˜nez, A.: A linea - ime solu ion o he Knapsack p ob-
lem using ac i e memb anes, Lec u e No es in Compu e Science, 2933 (2004), 140–
152.
[11] P´e ez-Jim´enez, M.J., Rome o-Campe o, F.J.: A CLIPS Simula o o Recognize P
Sys ems wi h Ac i e Memb anes, in his olume.
[12] Riscos-N´u˜nez, A., Gu i´e ez-Na anjo, M.A., P´e ez-Jim´enez, M.J.: Towa ds a p o-
g amming language in cellula compu ing, in his olume.
[13] CLIPS Web Page: h p:// www.ghg.ne /clips/CLIPS.h ml
[14] The P Sys ems Web Page: h p://psy ems.disco.unimib.i /
430