Solving the BINPACKING Problem by Recognizer P Systems with Active Membranes

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