Weak Metrics on Configurations of a P System

Weak Me ics on Con igu a ions o a P Sys em And ´es CORD ´ ON-FRANCO, Miguel A. GUTI´ ERREZ-NARANJO, Ma io J. P´ EREZ-JIM´ ENEZ, Agus ´ın RISCOS-N ´ U˜ NEZ 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: {aco don,magu ie ,ma pe , a iscosn}@us.es Abs ac . The e olu ion o a P sys em gene a es a ee o compu a ion po- en ially in ini e whe e i is e y di icul o se he deg ee o closeness be ween wo con igu a ions. The p oblem is specially ha d i we wan o quan i y ha p oximi y in o de o make use ul compa isons. In his pape we p opose some weak me ics on con igu a ions o a P sys em wi h a ixed s uc u e o mem- b anes and b ie ly discuss hei ad an ages and d awbacks. 1 In oduc ion In [2], a new model o compu a ion wi hin he amewo k o Na u al Compu ing was in oduced, called P Sys ems1. I s a s om he assump ion ha he p ocesses aking place in he compa men al s uc u e o a li ing cell can be in e p e ed as compu a ions. Roughly speaking, a P sys em consis s o a cell-like memb ane s uc u e, in he com- pa men s o which one places mul ise s o objec s which e ol e acco ding o gi en ules in a synch onous, pa allel, and non-de e minis ic manne . The memb ane s uc u e o a P sys em is a hie a chical a angemen o memb anes embedded in a skin memb ane, he one which sepa a es he sys em om i s en i onmen . A memb ane wi hou any memb ane inside is called elemen a y. Each memb ane de ines a egion ( he closed space delimi ed by a memb ane and by he memb anes immedia ely inside i ). The memb ane s uc u e o a P sys em 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 . The objec s can pass h ough memb anes and he memb anes can be dissol ed, di ided, o c ea ed. Acon igu a ion is he ins an aneous desc ip ion o he cu en memb ane s uc u e and he mul ise s o objec s associa ed wi h he memb anes. In each ime uni a ans o ma ion o a con igu a ion o he sys em akes place by applying he ules o each egion in a non- de e minis ic and maximally pa allel manne . In his way, one ge s ansi ions be ween he con igu a ions o he sys em and a sequence o ansi ions is called a compu a ion. In ce ain ci cums ances, we need o know how di e en wo con igu a ions o a P sys em a e. They can be di e en in many senses and he p oblem u ns ex emely ha d 1A layman-o ien ed in oduc ion can be ound in [3] and u he bibliog aphy a [5]. 139 when he con igu a ions do no co espond o he same P sys em. I we ha e h ee con- igu a ions C1,C2and C3, is C1mo e di e en om C2 han om C3? Is i possible o quan i y his deg ee o simila i y and gi e i an algeb aic ea men ? In his pape we s udy he di e ences among con igu a ions and we p opose a way o quan i y he deg ee o di e ence. We o e some solu ions o he p oblem o inding app op ia e me ics o P sys ems. We ocus ou a en ion only on inding me ics on he con igu a ions o a P sys em wi h a ixed memb ane s uc u e. This in ol es a ixed alphabe and a ixed se o ules. In his case, wo con igu a ions may only di e in he mul ise s associa ed wi h he memb anes. This di e ence can be measu ed be ween con igu a ions no necessa ily in he same b anch o a compu a ion o in he same s ep. We p opose wo models o de ining me ics. The i s one is based on he dis ance be ween egions. This gi es us a e y na u al way o de ining he dis ance acco ding o he di e ence be ween mul ise s, bu i does no conside he se o ules o he P sys em. The second model is based on he dependency g aph associa ed wi h he ules o a P sys em and is based on he sho es pa hs in his di ec ed g aph. The pape is o ganized as ollows. Sec ion 2 ecalls some ideas abou me ics and weak me ics in a gene al se up. In Sec ion 3 wo me ics on con igu a ions o P sys ems based on he di e en mul ise s o egions a e p esen ed. In Sec ion 4 a new concep in P sys em heo y is de ined: he dependency g aph o a P sys em. This dependency g aph is used in Sec ion 5 o de ine a weak me ic on con igu a ions. The pape inish wi h an example (Sec ion 6) and some inal ema ks. 2 Me ics Some imes i is necessa y o educe he ela ion be ween wo objec s o a numbe in o de o make compa isons and also pe o m algeb aic ope a ions wi h hem. This numbe is used o be called a dis ance and i allows us o di e en ia e be ween pai s o objec s in a simple way. So, o ins ance, we say ha wo owns Aand Ba e close han he owns C and Di he leng h o he sho es pa h om A o B(i.e., he dis ance which sepa a es hem) is less han he leng h o he sho es pa h om C o D. Analogously, ha dis ance can measu e he ime elapsed be ween wo e en s, he amoun o necessa y combus ible o co e a ou e, o he numbe o pieces which a e le o comple e a puzzle. In his way, i he dis ance om A o Bis less han he dis ance om A o C, we hink ha he ela ion be ween Aand Bis na owe han he ela ion be ween Aand C. Gi en a se X, i we associa e o e e y pai o elemen s (x, y)∈X×Xi s dis ance, we ge a mapping d:X×X→R. Bu , ob iously, no e e y mapping d:X×X→Ris a dis ance. Wha p ope ies does a mapping d:X×X→Rha e o sa is y in o de o be a dis ance? I is clea ha he c i e ion has o be weak enough o be common o he di e en dis ances o geome ic in ui ion and s ong enough o se le a solid heo y which allows us o deal wi h he concep o dis ance in abs ac si ua ions. I was M. F ´eche in his Ph.D. disse a ion [1] who s a ed ha i was su icien ha he mapping sa is ied •(∀x, y ∈X)d(x, y)=0⇔x=y, •(∀x, y ∈X)d(x, y) = d(y, x)( he condi ion o symme y), 140 ◦ ◦ ◦ ◦ ◦ ◦ dedmd ©©© © Figu e 1: Se e al me ics •(∀x, y, z ∈X)d(x, z)≤d(x, y) + d(y, z)( he iangle inequali y), o de elop a heo y o me ic spaces and, since hen, hey ha e been conside ed he basic pilla s o he heo y. As examples o dis ances based on he geome ic in ui ion, we can ci e h ee well-known dis ances in R2. Le A= (x1, y1) and B= (x2, y2) be wo poin s o he plane. •Euclidean dis ance (de):Gi en wo poin s Aand Bin R2, he dis ance demeasu es he leng h o he segmen which joins Aand B, i.e., o he sho es pa h om A o B, assuming ha he e a e no obs acles in he plane d(A, B) = p(x1−x2)2+ (y1−y2)2. •Manha an dis ance (dm):In his case, we also measu e he sho es pa h om A o B, bu in con as o he Euclidean dis ance, in he Manha an dis ance we sup- pose ha he mo es can only be ho izon al o e ical ones, simula ing he mo emen o a ehicle h ough s ee s wi h a g id o m. dm(A, B) = |x1−x2|+|y1−y2|. •Dis ance o he ain o es (d ):An example, pe haps less known, o dis ance in R2is his dis ance o he ain o es which also measu es he leng h o he sho es pa h be ween wo poin s. I ecei es his name because i s ands in R2 o he si ua ion o a ibe in a ain o es wi h a i e in y= 0. The people o he ibe, o each he wa e , ha e done b eaches pe pendicula o he i e . Due o he hick ain o es , i someone wan s o go om A o B, he only pa h is by he b eaches o on he bank. d (A, B) = ½|y1−y2|i x1=x2, |y1|+|y2|+|x1−x2|i x16=x2. A his poin , i makes sense o wonde why i is necessa y o de ine se e al dis ances on he same se . The answe is clea . E e y dis ance is adap ed o an ea lie s uc u e in he se . I we a e only in e es ed in endowing he se wi h a mapping which sa is ies he F ´eche ’s condi ions and we do no conside any o he p e ious ela ion among he membe s o he se , we can always conside he disc e e dis ance dd(A, B) = ½0 i A=B 1 i A6=B 141 which sa is ies he F ´eche ’s condi ions o be a dis ance, bu i would ha dly ha e a p ac- ical use ulness. A di e en si ua ion is se led when he p e–exis ing ela ion be ween he objec s is no symme ic. The numbe o kilome e s which sepa a e a own Aon he coas om a ano he a he op o a moun ain is independen o he di ec ion o he jou ney. Bu i ou idea o dis ance is he numbe o calo ies spen by a cyclis om a own o he o he , hen he condi ion o symme y is los in ou de ini ion o dis ance. A mo e ex eme case is he passage o ime. When Janua y 1s 2005 a i es, we will ha e o wai o 365 days o Janua y 1s 2006, bu when Janua y 1s 2005 a i es, i will no make sense o wai o he a i al o he yea 2004. Ano he eal li e si ua ion in which F ´eche ’s condi ions mus be weakened occu s when we go shopping. A good poin e o es ima e he di e ence be ween wo i ems can be he p ice, bu his is no exac ly a dis ance: We can ind wo dis inc i ems wi h he same p ice. 3 Me ics on Regions In his sec ion we p opose wo me ics on con igu a ions based on he di e en mul ise o he egions in each con igu a ion. Fo ha , we conside a P sys em wi h alphabe L and a ixed memb ane s uc u e, i.e., dissolu ion o duplica ion o memb anes a e no allowed. Since he memb ane s uc u e does no change along di e en con igu a ions, we also conside ha we can iden i y he same memb anes in di e en con igu a ions2. The me ics a e based on he di e ence be ween he mul ise s. Fi s ly, we de ine he dis ance be ween wo egions as he ca dinali y o he symme ical di e ence o hei associa ed mul ise s. We will use his de ini ion o measu e he dis ance be ween wo occu ences o he same memb ane in wo di e en con igu a ions. De ini ion 3.1 Le us conside a egion Rand L he alphabe o he P sys em. The mul ise associa ed wi h he egion R,MR, can be cha ac e ized as he mapping MR: L → N. The dis ance dRbe ween he egions R1and R2is de ined as dR(R1, R2) = X x∈L |MR1(x)− MR2(x)|, whe e |.|is he unc ion absolu e alue. Theo em 3.1 dRis a (weak) me ic be ween egions. 3.1 Plain Me ic Wi h he help o he dis ance dRbe ween egions, he de ini ion o he dis ance be ween con igu a ions is p e y na u al. As se o egions, he di e ence be ween con igu a ions is he sum o he di e ences be ween hei egions. Le Π be a P sys em in which he s uc u e o memb anes does no change du ing he compu a ion. In his P sys em, wo con igu a ions C1and C2only di e on he mul ise s associa ed o he egions, and he e o e, i Ri jis he egion delimi ed by he memb ane 2This can be done by conside ing labels, posi ions o some ype o enume a ion. 142 mjin he con igu a ion Ci(wi h j∈ {1, . . . , k}and i∈ {1,2}), hen we can conside he addi i e dis ance based on he dis ance be ween egions d+(C1, C2) = X 1≤j≤k dR(R1 j, R2 j). Theo em 3.2 d+is a (weak) me ic be ween con igu a ions. 3.2 Biased Me ic The (weak) me ic de ined abo e does no conside he ee s uc u e o he se o mem- b anes. We assume ha e e y memb ane has he same impo ance o measu e he close- ness be ween wo con igu a ions, so e e y elemen has he same weigh ega dless in which memb ane i occu s. Ne e heless, some imes we can ha e ano he poin o iew. Some imes, we design P sys ems whe e he inne memb anes wo k as pa allel de ices, sending ou o he skin he ou pu o each compu a ion. F om his poin o iew, he objec s in he skin, i.e., he esul o he pa allel compu a ion, a e mo e impo an han he objec s in each inne memb ane, since hese objec s only ha e a local unc ion. The (weak) me ic de ined below ollows his idea. Fi s ly we de ine a ecu si e dis ance dBamong egions: I {mj1, . . . , mjsj}a e he child en o he memb ane mj, hen we de ine dB(R1 j, R2 j) = dR(R1 j, R2 j) + Cj· sj X i=1 dR(R1 ji, R2 ji), whe e Cjis a cons an o bias associa ed wi h he memb ane mj. As a pa icula case o his de ini ion, we ha e he si ua ion in which mjis a lea e, i.e., mjhas no child en; hen dB(R1 j, R2 j) = d+(R1 j, R2 j). Finally, o de ine a mapping in o de o quan i y he closeness be ween con igu a ions, we only ha e o conside he dis ance be ween hei skins3. I msis he skin memb ane, hen dB(C1, C2) = dB(R1 s, R2 s). No e ha i all he cons an s o bias a e equal o 1, hen d (C1, C2) = d+(C1, C2). Theo em 3.3 dBis a (weak) me ic be ween con igu a ions. 4 Dependency G aphs In his sec ion we explo e a new a ian o me ics be ween con igu a ions based on he dependence among elemen s o he alphabe wi h espec o he se o ules o he P sys em. To his aim, we conside he ules o a P sys em wi h a new ep esen a ion and we de ine he concep o con luence o compu a ions in a mo e gene al way han he s anda d one. The ules o a non-coope a i e P sys em, wi hou dissolu ion no di ision i in o he ollowing schema (e0, µ1)→(e1, µ2),(e2, µ2), . . . , (en, µ2) 3Fo he sake o simplici y, we keep he same no a ion dBalso o con igu a ions. 143 which can be in e p e ed as ollows: The occu ence o he elemen e0in he memb ane µ1 igge s he ule and p o okes he appa i ion o he mul ise e1e2. . . enin o he memb ane µ2.Ob iously, i µ1=µ2, hen we ha e an e olu ion ule, i n= 1 and µ1is a a he o µ2, hen we ha e a send-in communica ion ule, and i µ1is a child o µ2, hen we ha e a send-ou communica ion ule. The pai (e0, µ1) is he le side o he ule and he mul ise o pai s (e1, µ2),(e2, µ2), . . . , (en, µ2) is he igh side o he ule. Nex , we de ine he g aph o dependence o a P sys em based on his new ep esen a ion o he ules. De ini ion 4.1 The dependency g aph o a P sys em Πis a pai GΠ=hVΠ, EΠisuch ha VΠis he se o all he pai s (e, µ)whe e eis an elemen o he language and µis a memb ane and EΠis he se o all he o de ed pai s o elemen s o VΠ,h(e1, µ1),(e2, µ2)i such ha (e1, µ1)is he le side o a ule and (e2, µ2) belongs o he igh side o a ule. We illus a e his de ini ion wi h an example. Le us conside he nex oy P sys em Π, wi h alphabe Γ = {a, b, c, d, z}, memb ane s uc u e [s[e]e]sand se o ules: Rule 1: [ea]e→a[e]e Rule 2: [sa]s→a[s]s Rule 3: [ea]e→[ebz]e Rule 4: [eb]e→c[e]e Rule 5: [sc]s→[sdz]s Rule 6: [sd]s→a[s]s In o de o de ine he dependency g aph, we ha e o conside he se o memb anes {e, s}, and since he elemen s can be sen ou o he sys em ( ules 2and 6), we will conside a new egion ou side as a place whe e he elemen s can s and, so he se o egions becomes {e, s, ou side}. Finally, wi h he new ep esen a ion, he ules can be w i en as ollows: Rule 1: (a, e)→(a, s) Rule 2: (a, s)→(a, ou side) Rule 3: (a, e)→(b, e),(z, e) Rule 4: (b, e)→(c, s) Rule 5: (c, s)→(d, s),(z, s) Rule 6: (d, s)→(a, ou side) The e o e, he dependency g aph o Π, GΠ=hVΠ, EΠiis de ined by he ollowing se s: VΠ=   (a, e) (b, e) (c, e) (d, e) (z, e) (a, s) (b, s) (c, s) (d, s) (z, s) (a, ou side) (b, ou side) (c, ou side) (d, ou side) (z, ou side)    The se o e ices VΠhas 15 elemen s, bu 7 o hem a e isola ed e ices: only 8 e ices occu in some edge (see Figu e 2). EΠ=            h(a, e),(b, e)i,h(a, e),(z, e)i,h(a, e),(a, s)i, h(a, s),(a, ou side)i, h(b, e),(c, s)i, h(c, s),(d, s)i,h(c, s),(z, s)i, h(d, s),(a, ou side)i            144 (z,e) (a,e) (b,e) (a,s) (c,s) (z,s) (a,ou side) (d,s) ¾ - - - - ? 6 ? (c,ou side) (b,ou side) (z,ou side) (d,ou side) (d,e) (c,e) (b,s) Figu e 2: The dependency g aph No e ha he dependency g aph only depends on he memb ane s uc u e and he se o ules o he P sys em and no on he elemen s o he memb anes a he ini ial momen . The example will help us o in oduce a new de ini ion o con luence, mo e gene al han he usual one. We know he s uc u e o memb anes and he se o ules o ou oy P sys em. A he beginning we will conside he skin emp y and he inne memb ane con aining only copies o he elemen a. The in ended compu a ion sends ou o he sys em, in se e al s eps, as many copies o aas in oduced a he beginning in he memb ane e. Figu e 3 shows he compu a ion ee o he P sys em when wo copies o aa e in oduced in he memb ane e. The sys em is non-de e minis ic. In he i s s ep he ules 1and 3 can be igge ed. This p oduces h ee di e en b anches. The h ee b anches end and he inal con igu a ion is di e en in all he cases, bu always in he end o he compu a ion he P sys em sends ou as many copies o aas in oduced in he inne memb ane. As a compu a ional de ice, we can hink ha he P sys em wo ks, as e e y b anch e u ns he co ec numbe o a. This leads us o de ine a mo e gene al de ini ion o con luence han he classical one4: he con luence wi h espec o a p ope y. De ini ion 4.2 A P sys em is called con luen wi h espec o a p ope y i all he b anches o he compu a ion ee end, and all he inal con igu a ions sa is y he p op- e y. Wi h his de ini ion, we can say ha he P sys em in he example (wi h a2in he memb ane ea he beginning) is con luen wi h espec o he p ope y: The numbe o objec s ain he en i onmen in he inal con igu a ion is wo. No e ha he h ee b anches in he example end wi h a co ec con igu a ion, bu he numbe o s eps is no he same in all hem. This sugges s us a way o compu e how a om each o he wo con igu a ions a e. Be o e gi ing he de ini ion o he weak me ic on con igu a ions, we need some p e ious de ini ions. De ini ion 4.3 Gi en a P sys em, an L-con igu a ion o he P sys em is a mul ise o pai s (s, m)whe e sis an elemen o he alphabe and mis a memb ane o he P sys em. We will say ha an L-con igu a ion is o al when o all symbol so he alphabe and o all memb ane m, he mul iplici y o sin mis he same as he mul iplici y o he pai 4See, o example, [4]. 145 s e a2 s ea2 s ea2 s e bz a s e z c a s e b2z2 s e z2c2 s e zdz a s e z z a2 s e z2d2z2 s e z2z2a2 ? ?? ? ? ? ? ? ? ? 6 5 2,4 1,3 6,6 5,5 4,4 3,3 2,2 1,1 Figu e 3: The compu a ion ee (s, m)in he con igu a ion. Any p ope submul ise o a o al L-con igu a ion is a pa ial L-con igu a ion. The dis ance be ween wo nodes o he dependency g aph is de ined in he na u al way: De ini ion 4.4 Gi en a di ec ed g aph (as a dependency g aph), a pa h om wo e ices aand bis a ini e sequence 0, 1, . . . , no e ices such ha 0=a, n=band o all i∈ {0, . . . , n −1},( i, i+1)is an edge o he g aph. The sequence o e ices wi h an unique e ex is also conside ed a pa h. The leng h o a pa h is he numbe o e ices o he sequence minus one. Gi en a e ex , we de ine he se o ini ial e ices o ,I as he se o all he e ex ao he g aph such ha he e exis s a pa h om a o . Gi en a se o e ices S, we de ine he se o ini ial e ices o S,ISas he se o all he e ex ao he g aph such ha he e exis s a e ex in Sand a pa h om a o . De ini ion 4.5 Gi en a P sys em Πand i s dependency g aph GΠ, he dis ance be ween wo nodes 1and 2o GΠis he leng h o he sho es pa h ha connec 1and 2and in ini e i he e is no pa h om 1 o 2. 146 5 Weak Me ics Based on he Dependency G aph 5.1 Fi s App oach In non-de e minis ic P sys ems, gi en a con igu a ions he e (po en ially) exis se e al con igu a ions which can be eached. I he P sys em is con luen in he classical sense, om he poin o iew o co ec ness, i is no impo an he b anch we ollow, because he inal esul is he same, bu om a compu a ional poin o iew, he cos measu ed as he numbe o s eps in he compu a ion can be di e en , so i can be in e es ing o de ine some kind o measu e o how a a con igu a ion is om he inal con igu a ion. Nex , le us conside a o al L-con igu a ion C, which ep esen s an in e media e s ep o he compu a ion, and a pa ial L-con igu a ion F, which ep esen s he p ope y o a possible inal L-con igu a ion. How can we measu e he closeness be ween hem? One way is by using he minimum numbe o s eps o compu a ion be ween hem in he na u al way. Fi s ly, we conside an elemen b∈ F. The elemen bhas o be eachable om he elemen s in C, and we a e in e es ed in he sho es pa h, so we conside min a∈C∩Ib d(a, b), whe e C ∩ IFis he in e sec ion o he L-con igu a ion Cwi h he se o ini ial e ices o F, in o he wo ds, is he mul ise o all he elemen s ao Csuch ha such ha he e exis s a pa h om a o b. I his se is emp y, he minimum is in ini e. Finally, o compu e he dis ance, we ha e o conside he longes o hese sho es pa hs. De ini ion 5.1 Gi en wo L-con igu a ions Cand F, he quasi-me ic om C o Fis de ined as d(C,F) = max b∈F {min a∈C∩Ib d(a, b)}. Theo em 5.1 dis a (weak) me ic be ween L-con igu a ions. The me ic dhinduced by his quasi-me ic, dh(C1,C2) = max{d(C1,C2), d(C2,C1)}, is he Hausdo me ic on he L-con igu a ions. 6 Example In ou example, in he i s s ep o he compu a ion h ee new con igu a ions a e possible (see Figu e 3). They can be ep esen ed as he ollowing mul ise s C1={(a, s),(a, s)}, C2={(b, e),(z, e),(a, s)}, C3={(b, e),(b, e),(z, e),(z, e)}, and he pa ial L-con igu a ion which cha ac e izes all he inal con igu a ions is F={(a, ou side),(a, ou side)}; 147