A Prolog Simulator for Deterministic P Systems with Active Membranes

A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes A. CORD´ ON-FRANCO, M.A. GUTI´ ERREZ-NARANJO, M.J. P´ EREZ-JIM´ ENEZ, F. SANCHO-CAPARRINI Dp o. de Ciencias de la Compu aci´on e In eligencia A i icial E.T.S. Ingenie ´ıa In o m´a ica. Uni e sidad de Se illa A da. Reina Me cedes s/n, 41012, Se illa, Espa˜na {aco don, magu ie , ma pe , sancho}@us.es Abs ac In his pape we p opose a new way o ep esen P sys ems wi h ac i e memb anes based on Logic P og amming echniques. This ep esen a ion allows us o exp ess he se o ules and he con igu a ion o he P sys em in each s ep o he e olu ion as li e als o an app op ia e language o i s o de logic. We p o ide a P olog p og am o simula e he e olu ion o hese P sys ems and p esen some auxilia y ools o simula e he e olu ion o a P sys em wi h ac i e memb anes using 2-di ision which sol es he SAT p oblem ollowing he echniques p esen ed in 10). Keywo ds Logic p og amming, Memb ane compu ing, Simula ion, P olog, SAT-p oblem §1 In oduc ion In 5), a new model o compu a ion wi hin he amewo k o Na u al Compu ing was in oduced, called P Sys ems. I is based upon he no ion o memb ane s uc u e ha is used o enclose compu ing cells in o de o make hem independen compu ing uni s. Also, a memb ane se es as a communica ion channel be ween a gi en cell and o he cells “adjacen ” o i . This model comes om he obse a ion ha he p ocesses 2A. Co d´on-F anco e al. which ake place in he complex s uc u e o a li ing cell can be conside ed as compu a ions. Since hese compu ing de ices we e in oduced se e al a ian s ha e been conside ed. See 6) o a ai ly comple e compendium abou P sys ems. The di e en a ian s o P sys ems ound in he li e a u e a e gene ally hough as gene a ing de ices. Many o hem ha e been p o ed o be compu a- ionally comple e 6). The model we s udy he e, P sys ems wi h ac i e memb anes, wo ks wi h symbol–objec s, and i p o ides ules o memb ane di ision. In pa icula , P sys ems wi h ac i e memb anes a e s udied in 6), sec ion 7.2. The main goal o his pape is o p opose and illus a e a ep esen a ion o P sys ems wi h ac i e memb anes based on Logic P og amming echniques. The pape is o ganized as ollows: Sec ion 2 b ie ly p esen s some ideas abou he con enience o using P olog as he basis o his ep esen a ion; Sec ion 3 in oduces he way o ep esen all basic ing edien s o his model; Sec ion 4 s udies he designed algo i hm o simula e de e minis ic P sys ems wi h ac i e memb anes; Sec ion 5 p esen s as an example he solu ion gi en o SAT p oblem using his model in 10); Sec ion 6 p esen s some conclusions and u u e wo k abou he possibili ies o his new simula o and ep esen a ion echniques using Logic P og amming; inally, he Appendix shows a s anda d wo k session wi h he in e ace p o ided wi h he simula o . §2 Why P olog? Choosing a p og amming language o an e ec i e implemen a ion o a P sys em simula o is no an easy decision. The language has o be exp essi e enough o handle symbolic knowledge in a na u al way and he abili y o e ol ing he di e en con igu a ions ollowing a se o ules. P olog∗1has bo h hese ea u es. On one hand, he based- ee da a s uc u e and he use o in ix ope a o s de ined ad hoc by he p og amme allow us o simula e he na u al language and he use can ollow he e olu ion o he sys em wi hou any knowledge o P olog (see sec ions 3.2 and 3.3). On he o he hand, P olog p og ams a e se s o ac s and ules and basic mechanisms o P olog a e pa e n ma ching and au oma ic back acking, so he design o he in e ence engine o pe o m he e olu ions has a na u al ea men om a p og amme poin o iew. ∗1A good s a ing poin can be 3) o 13). A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 3 Finally, he use o P olog as p og amming language has o he desi able side e ec s which a e ou o he scope o his pape . P olog i s in o all kinds o symbolic easoning and he use o his ep esen a ion can be a way o link P sys ems o o he deeply s udied ields in A i icial In elligence. §3 A Logic P og amming ep esen a ion o P sys ems wi h ac i e memb ane Following 6) aP sys em wi h ac i e memb anes is a cons uc : Π = (V, H, µ, w1, . . . , wm, R), whe e: 1. m≥1, is he ini ial deg ee o he sys em; 2. Vis 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. w1, . . . , wma e s ings o e V, 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. [hx→u]α h, o h∈H,α∈ {+,−,0},x∈V,u∈V∗. This is an objec e olu ion ule, associa ed wi h a memb ane labelled wi h h and depending on he pola i y o ha memb ane, bu no di ec ly in ol ing he memb ane. b. x[h]α1 h→[hy]α2 h, o h∈H,α1, α2∈ {+,−,0},x, y ∈V. 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 , and simul aneously i s pola i y can be changed. c. [hx]α1 h→[h]α2 hy, o h∈H,α1, α2∈ {+,−,0},x, y ∈V. 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 a- neously he pola i y o he memb ane can be changed. d. [hx]α h→y, o h∈H,α∈ {+,−,0},x, y ∈V. A memb ane labelled wi h his dissol ed in eac ion wi h an objec . The skin is ne e dissol ed. e. [hx]α1 h→[hy]α2 h[hz]α3 h, o h∈H,α1, α2, α3∈ {+,−,0},x, y, z ∈V. An elemen a y memb ane can be di ided in o wo memb anes wi h 4A. Co d´on-F anco e al. he same label, possibly ans o ming some objec s and pola i y. 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 nonde 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, hen i s con en (mul ise and in e nal mem- b anes) is le ee in he su ounding egion. •All objec s and memb anes no speci ied in a ule and which do no e ol e emain unchanged o he nex s ep. •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). In o de o gi e a o mal ep esen a ion in P olog o he basic s uc u es o P sys ems wi h ac i e memb anes using 2-di ision, he ollowing ep esen a ion will be conside ed. 3.1 Rep esen a ion o memb ane s uc u es A gi en con igu a ion will be exp essed by means o a labelled ee, whe e: 1. < > is he posi ion o deno e he oo o he ee and i will be associa- ed o he skin; 2. i < i1, . . . , in>is he posi ion o a memb ane h, hen < i, i1, . . . , in> will deno e he posi ion o he i- h in e nal memb ane o h. The e exis s one di e ence be ween he abo e ep esen a ion and he one we use in P olog: in ou P olog ep esen a ion, i in one s ep o he compu a ion a memb ane wi h label < i1, . . . , in>has kin e nal memb anes, hen i s child en do no ha e o be labelled wi h <1, i1, . . . , in>,<2, i1, . . . , in>,. . . ,< k −1, i1, . . . , in>,< k, i1, . . . , in>. This is because i one child memb ane is dissol ed, he o he ones a e no e- A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 5 labelled. Besides, new memb anes ob ained by di ision a e labelled wi h new indexes, no by illing he holes o p e iously dissol ed memb anes. 3.2 Rep esen a ion o con igu a ions Le us emembe ha o gi e a con igu a ion o a P sys em wi h ac i e memb anes consis s in making explici he memb ane s uc u e and he con en o e e y memb ane p esen in his s uc u e. In ou model we will ep esen he con igu a ion in one s ep o he e o- lu ion as a se o one-li e al clauses, each o hem ep esen ing each ali e mem- b ane. Hence, in his ep esen a ion each clause will show he label, posi ion, pola i y, mul ise o objec s and cu en s ep o he compu a ion, as well as he P sys em his memb ane belongs o. In his way, he se o clauses gi es in o - ma ion abou he con en s o he memb anes and he memb ane s uc u e (by means o he posi ion o each one). In a gene al o m, o deno e ha in he - h s ep o i s e olu ion he P sys em, P, has a memb ane a posi ion [pos] wi h label h, pola i y αand mas mul ise , we will w i e P:: hec αa [pos]wi h ma ime No e ha we can use he use - iendly ep esen a ion o a P olog li e al, ins ead o he unc ional ep esen a ion. In a gene al way, i m={{x1, . . . , xn}} (wi h no necessa ily xi6=xj), hen we will deno e m= [x1, . . . , xn]. 3.3 Desc ip ion o he ules By means o some new unc ion symbols, he ules a e also ep esen ed as li e als. In wha ollows we p esen he gene al o m o he di e en ules showed abo e: (a) [hx→u]α h P ule xe ol es o [u]in hec α (b) x[h]α1 h→[hy]α2 h P ule xou o hec α1sends in yo hec α2 (c) [hx]α1 h→[h]α2 hy P ule xinside o hec α1sends ou yo hec α2 (d) [hx]α h→y P ule xinside o hec αdissol es and sends ou y 6A. Co d´on-F anco e al. (e) [hx]α1 h→[hy]α2 h[hz]α3 h P ule xinside o hec α1di ides in o yinside o h ec α2and zinside o hec α3 §4 The algo i hm The P olog algo i hm o simula e a P sys em wo ks in a na u al way. The inpu o he p og am is he ini ial con igu a ion o he memb anes (which is ep esen ed as a se o li e als wi h p edica e symbol **, all o hem a ime 0) and an app op ia e se o ules. •S ep 1: Ini ializa ion. A he beginning, all he memb anes a e se o applicable and hei objec s a e spli in o wo mul ise : one usable mul ise , con aining all he objec s o he ini ial memb ane, and one used mul ise which is emp y. •S ep 2: T ansi ion. I he e exis s an applicable memb ane sa is ying he condi ion o a ule, hen he ule is applied in he ollowing way: – (a)-s ep: A his s age, only ules o ype (a) a e checked. The ob- jec which igge s he ule is emo ed om he usable and he esul mul ise by he applica ion o he ule is added o used, o p e en ha he same objec is used by wo di e en ules a he same s ep. A e he e olu ion s ep, he memb ane emains o be applicable and new e olu ion ules can be applied. This s age ends when no mo e ules o ype (a) can be applied. – Non-(a)-s ep: A his s age, only one ule o he o he ypes (no (a)) can be applied. Le us emembe ha his simula ion only wo ks wi h de e minis ic P sys ems (in ac , i wo ks wi h con luen ones). The ac ion depends on he kind o ule o apply: ∗Send ou ule: The elemen which igge s he ule is emo ed om usable mul ise and he new one is added o he used mul ise o he a he memb ane. Bo h memb anes changes o no applicable mode. I he elemen is sen ou o he skin, hen i is ma ked wi h he p ope y ou side. ∗Send in ule: I is he ecip ocal o he p e ious one. The ele- men which igge s he ule is emo ed om usable in he a he memb ane and he new one is added o he used mul ise . Bo h memb anes changes o no applicable mode. ∗Dissolu ion ule: The elemen which igge s he ule belongs o A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 7 usable and he new elemen ob ained oge he wi h he es o he elemen s o he memb ane a e added o he used mul ise o he a he memb ane. When a memb ane mis dissol ed, i s inne mem- b anes (i.e. i s child en) become child en o he a he memb ane o min he nex s age o e olu ion. Fo ha , he new posi ions ha e o be a anged. The a he memb ane changes o no applicable mode. ∗Di ision ule: The elemen which igge s he ule belongs o us- able and he di ision c ea es wo new memb anes in no applicable mode. One o hem keeps he o iginal posi ion and he second one ge s a posi ion which has no been occupied by any memb ane. – End: When no mo e ules can be applied o applicable memb anes, a new con igu a ion (wi h a ime inc emen ed by 1) is s o ed. In his momen no memb ane has applicable o no applicable s a e. These modes only ha e alidi y du ing he e olu ion. A his s age, he P sys em is eady o a new s ep o he e olu ion. •S ep 3: End o compu a ion. The e olu ion o he P sys em inishes when he e a e no ules o be applied. No ice ha due o he ea u es o he implemen a ion, he p og am only ensu es a co ec simula ion o he e olu ion o de e minis ic (con luen ) P sys ems. Ne e heless, mos o he usual algo i hms ha sol e in e es ing p oblems a e co e ed. §5 A s udy case: SAT p oblem 5.1 A linea solu ion o he SAT p oblem by P sys ems wi h ac i e memb anes P oposi ional Sa is iabili y is he p oblem o de e mining, o a o mula o he p oposi ional calculus, i he e is an assignmen o u h alues o i s a iables o which ha o mula e alua es o ue. By SAT we mean he p oblem o p oposi ional sa is iabili y o o mulas in conjunc i e no mal o m (CNF). Following 10) we p esen a amily o ecognizing P sys ems wi h ac i e memb anes using 2–di ision (see 6), sec ion 7.2) sol ing he SAT p oblem in linea ime. Le us suppose ha ϕ=C1∧· · ·∧Cmin CNF and V a (ϕ) = {x1, . . . , xn}. Fo each (m, n)∈N2we conside he ecognizing P sys em (Π(hm, ni),Σ(m, n), i(m, n)), 8A. Co d´on-F anco e al. whe e Σ(m, n) = {xi,j, xi,j : 1 ≤i≤m, 1≤j≤n},i(m, n) = 2 and Π(hn, mi) = (Γ(m, n),{1,2},[1[2]2]1, w1, w2, R) is de ined as ollows: Γ(m, n) = Σ(m, n)∪ {ck: 1 ≤k≤m+ 2}∪{dk: 1 ≤k≤3n+ 2m+ 3} ∪ { i,k : 0 ≤i≤m, 1≤k≤2n} ∪ {e, }∪{Y es, No}. We will say ha e e y in e nal memb ane wi h label 2 is an in e nal memb ane. The ini ial con en o each memb ane is: w1=∅and w2={d1}. The se Ro ules is gi en by: (a){[2dk]0 2→[2dk]+ 2[2dk]− 2: 1 ≤k≤n}. By using a ule o (a), a memb ane wi h label 2 is di ided in o wo memb anes wi h he same label, bu wi h di e en pola iza ions. These ules allow us o duplica e, in one s ep, he o al numbe o in e nal memb anes. (b){[2xi,1→ i,1]+ 2,[2xi,1→ i,1]− 2: 1 ≤i≤m}, {[2xi,1→λ]− 2,[2xi,1→λ]+ 2: 1 ≤i≤m}. The ules o (b) y o implemen a p ocess allowing o he in e nal mem- b anes o encode he assignmen o a a iable and, simul aneously, o check he alue o all clauses by his assignmen , in such a way ha i he clause is ue, hen an objec i,1will appea in he memb ane. In o he case, he objec encoding he a iable will disappea . (c){[2xi,j →xi,j−1]+ 2,[2xi,j →xi,j−1]− 2: 1 ≤i≤m, 2≤j≤n}, {[2xi,j →xi,j−1]+ 2,[2xi,j →xi,j−1]− 2: 1 ≤i≤m, 2≤j≤n}. The check p ocess desc ibed p e iously is always made wi h espec o he i s a iable appea ing in he in e nal memb ane. Hence, he ules o (c) ake cha ge o making a cyclic pa h h ough all he a iables o ge ha , ini ially, he i s a iable is x1, hen x2, and so on. (d){[2dk]+ 2→[2]0 2dk, , [2dk]− 2→[2]0 2dk: 1 ≤k≤n}, {dk[2]0 2→[2dk+1]0 2: 1 ≤k≤n−1}. The ules o (d) a e used as con olle s o he gene a ing p ocess o he assignmen s and he encoding o he sa is ied clauses: he objec s da e sen ou o he skin a he same ime he checking is made and hey come back o he in e nal memb anes o s a he di ision o hese memb anes. (e){[2 i,k → i,k+1]0 2: 1 ≤i≤m, 1≤k≤2n−1}. A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 9 The use o objec s in he ules (i), (j) and (k) makes necessa y o pe o m a o a ion o hese objec s. This is he mission o he ules o (e). ( ){[1dk→dk+1]0 1:n≤k≤3n−3}; [1d3n−2→d3n−1e0]0 1. Th ough he coun e -objec s d, he ules o ( )con ol he o a ion o he elemen s i,k in he in e nal memb anes. (g)e[2]0 2→[2c1]+ 2; [1d3n−1→d3n]0 1. The applica ion o he ules o (g) will show ha he sys em is eady o check which clauses a e made ue by he assignmen encoded by an in e nal memb ane. (h){[1dk→dk+1]0 1: 3n≤k≤3n+ 2m+ 2}. The ules o (h) supply coun e s in he skin h ough objec s d, in such a way ha , i objec s d3n+2mappea , hen hey show he end o he checking o he clauses. The objec s dk, wi h 3n+ 2m+ 1 ≤k≤3n+ 2m+ 3, will con ol he inal s age o he compu a ion. (i) [2 1,2n]+ 2→[2]− 2 1,2n. The applicabili y o he ule (i) encodes he ac ha an in e nal mem- b ane makes ue he clause ep esen ed by he objec 1,2n, h ough a change in he sign o i s pola iza ion. Because o his, we mus elabel he alues o ep esen ing he di e en in e nal memb anes. This is done by means o he ules (j). (j){[2 i,2n→ i−1,2n]− 2: 1 ≤i≤m}. (k) 1,2n[2]− 2→[2 0,2n]+ 2. By using he ule (k) he ask o making explici he assignmen s ha make ue he clause encoded in ha momen o he execu ion by he objec 1,2nis ended. (l){[2ck→ck+1]− 2: 1 ≤k≤m}. The p esence o objec s ck(wi h 2 ≤k≤m+ 1) in he in e nal mem- b anes shows ha he assignmen s making ue e e y clause a e being de e mined. (m) [2cm+1]+ 2→[2]+ 2cm+1. 16 A. Co d´on-F anco e al. 13) Logic P og amming: h p://www.a m.sbu.ac.uk/logic-p og/ §7 Appendix In wha ollows we p esen a sample o he ules w i en in he o ma hey mus be gi en o he simula o ∗3. % Se (a) p1 ule d1 inside_o e2 ec 0 di ides_in o d1 inside_o e2 ec 1 and d1 inside_o e2 ec-1 ** 1. p1 ule d2 inside_o e2 ec 0 di ides_in o d2 inside_o e2 ec 1 and d2 inside_o e2 ec-1 ** 2. % Se (b) p1 ule x1_1 e ol es_ o [ 1_1]in e2 ec 1 ** 3. p1 ule z1_1 e ol es_ o [ 1_1]in e2 ec-1 ** 4. ... % Se (c) p1 ule x1_2 e ol es_ o [x1_1]in e2 ec 1 ** 11. p1 ule x1_2 e ol es_ o [x1_1]in e2 ec-1 ** 12. p1 ule z1_2 e ol es_ o [z1_1]in e2 ec 1 ** 13. ... % Se (d) p1 ule d1 inside_o e2 ec 1 sends_ou d1 o e2 ec 0 ** 19. p1 ule d1 inside_o e2 ec -1 sends_ou d1 o e2 ec 0 ** 20. ... % Se (e) p1 ule 1_1 e ol es_ o [ 1_2] in e2 ec 0 ** 24. p1 ule 1_2 e ol es_ o [ 1_3] in e2 ec 0 ** 25. ... % Se ( ) p1 ule d2 e ol es_ o [d3] in e1 ec 0 ** 30. p1 ule d3 e ol es_ o [d4] in e1 ec 0 ** 31. p1 ule d4 e ol es_ o [d5, e] in e1 ec 0 ** 32. % Se (g) p1 ule e ou _o e2 ec 0 sends_in c1 in o e2 ec 1 ** 33. p1 ule d5 e ol es_ o[d6]in e1 ec 0 ** 34. % Se (h) ∗3The numbe a e ** is he o dinal associa ed o he ule. A P olog Simula o o De e minis ic P Sys ems wi h Ac i e Memb anes 17 p1 ule d6 e ol es_ o [d7] in e1 ec 0 ** 35. ... p1 ule d12 e ol es_ o [d13]in e1 ec 0 ** 41. % Se (i) p1 ule 1_4 inside_o e2 ec 1 sends_ou 1_4 o e2 ec-1 ** 42. % Se (j) p1 ule 1_4 e ol es_ o [ 0_4] in e2 ec -1 ** 43. p1 ule 2_4 e ol es_ o [ 1_4] in e2 ec -1 ** 44. % Se (k) p1 ule 1_4 ou _o e2 ec-1 sends_in 0_4 in o e2 ec 1 ** 45. % Se (l) p1 ule c1 e ol es_ o [c2] in e2 ec -1 ** 46. p1 ule c2 e ol es_ o [c3] in e2 ec -1 ** 47. % Se (m) p1 ule c3 inside_o e2 ec 1 sends_ou c3 o e2 ec 1 ** 48. % Se (n) p1 ule c3 e ol es_ o [c4, ] in e1 ec 0 ** 49. % Se (o) p1 ule inside_o e1 ec 0 sends_ou o e1 ec 1 ** 50. % Se (p) p1 ule c4 inside_o e1 ec 1 sends_ou yes o e1 ec-1 ** 51. % Se (q) p1 ule d13 inside_o e1 ec 0 sends_ou no o e1 ec 1 ** 52.