A Note on Complexity Measures for Probabilistic P Systems

A No e on Complexi y Measu es o P obabilis ic P Sys ems And ´es Co d´on-F anco, Fe nando Sancho-Capa ini (Uni e si y o Se illa, Spain {aco don, sancho}@us.es) Abs ac : In his pape we p esen a fi s app oach o he defini ion o diffe en en opy measu es o p obabilis ic P sys ems in o de o ob ain some quan i a i e pa ame e s showing how complex he e olu ion o a P sys em is. To his end, we define wo possible measu es, he fi s one o eflec he en opy o he P sys em conside ed as he s a e space o possible compu a ions, and he second one o eflec he change o he P sys em as i e ol es. Key Wo ds: P sys ems, En opy, Na u al Compu ing Ca ego y: F.1.1, G.2.2, H.1.1 1 In oduc ion In [P˘aun 00] Gh. P˘aun in oduced a new compu ing de ice, called P sys em, wi hin he amewo k o Na u al Compu ing 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 hen, hese complex sys ems ha e been in es iga ed om many poin s o iew. Fo ins ance, hey ha e been shown o be able o sol e ha d p oblems in lowe ime han classical de ices. S a ing om an ini ial s a e, hey e ol e by means o ules ha can modi y he objec s inside he sys em and e en he sys em own s uc u e. I we look a P sys ems as p obabilis ic de ices whe e se e al diffe en com- pu a ions can be eached om a gi en ini ial s a e, i is in ui i ely ob ious ha some unce ain y in he esul p o ided by he P sys em a ises. In o de o define some quan i a i e p ope y allowing us o measu e his unce ain y, we begin wi h some gene al obse a ions abou he no ion o a sys em. A common-sense defini ion o he no ion o a sys em is a g oup o uni s so combined as o o m a whole and o ope a e in unison. The e a e se e al o he defini ions in he li e a u e. Fo example, a echnical defini ion was p esen ed by Hall and Fagan [Hall and Fagan 80]: A sys em is a se o objec s oge he wi h ela ionships be ween he objec s. Fo malis s p esen a e y simple and gene al defini ion: gi en a amily o base se s X1,...,X n, a sys em Sis any ela ion (sub- se ) in X=Πn i=1Xi. Cons uc i is s disag ee wi h his o malis poin o iew, emphasizing ha he na u al wo ld o e ol ing sys ems can ne e be cap u ed by o mal sys ems wi h an ap io ifixed and fini e amoun o base se s; hence, Jou nal o Uni e sal Compu e Science, ol. 10, no. 5 (2004), 559-566 submi ed: 1/4/04, accep ed: 10/4/04, appea ed: 28/5/04 © J.UCS hey p opose open sys ems which define hei elemen s and base se s du ing he p ocesses o hei e olu ion. Ne e heless, he e a e some common cha ac e is ics in all app oaches abo e: –A a ie y o dis inc en i ies. –These en i ies a e in ol ed in some kind o ela ions. –These ela ions a e sufficien o gene a e a new en i y, o a highe complexi y. In he las 20 yea s, he s udy o complex sys ems has eme ged as a ecognized field in i s own igh , al hough a good defini ion o wha a complex sys em is has eluded igo ous o mula ion. A emp s o o malize he concep o complexi y go back e en u he , o Shannon’s In o ma ion Theo y [Shannon 48], whe e he concep s o en opy and in o ma ion o a sys em (as measu es o unce ain y and a ie y) we e defined. 2 En opy and In o ma ion The s a e space,S, o a sys em is he se o all possible s a es ha he sys em can be in. An essen ial componen in he s udy o a sys em is a quan i a i e measu e o he size o i s s a e space. This measu e is usually called a ie y and i ep esen s he eedom o he sys em o each a pa icula s a e, and hus he unce ain y we ha e abou which s a e he sys em is in. The a ie y, V,is defined as he numbe o elemen s in he s a e space o , mo e commonly, as V=log 2(|S|), i we encode he s a es o he sys em by bi s. A a ie y o one bi , V= 1, means ha he sys em has wo possible s a es, ha is, one choice. In he case o nbina y a iables, V=log 2(2n)=nis he e o e equal o he numbe o independen choices. Thus, he sys em a ie y, V, measu es he numbe o possible s a es he sys- em can exhibi , and co esponds o he numbe o independen bina y a iables. Bu , in gene al, he a iables used o desc ibe a sys em a e nei he bina y no independen . I he ac ual a ie y o s a es ha he sys em can exhibi is smalle han he a ie y o s a es we can po en ially concei e, hen we say ha he sys- em is cons ained, wha means ha he sys em canno make a ull use o he a ailable eedom, because some in e nal o ex e nal laws do no allow ce ain combina ions o alues o he a iables. The cons ain educes ou unce ain y abou he sys em s a e. Hence, he cons ain ,C, o he sys em can be defined as he diffe ence be- ween maximal and ac ual a ie y: C=Vmax −V. 560 Co don-F anco A., Sancho-Capa ini F.: A No e on Complexi y Measu es ... The a ie y and cons ain can be gene alized o a p obabilis ic amewo k, whe e hey a e eplaced by en opy and in o ma ion, espec i ely. Le us suppose ha we do no know he p ecise s a e, s, o a sys em, bu only he p obabili y dis ibu ion, P(s), o he sys em o be in s a e s.The gene aliza ion o he a ie y o he sys em can hen be exp essed as en opy H: H(P)=− s∈S P(s)·log(P(s)). H eaches i s maximum alue when all s a es a e equip obable, ha is, when we ha e no in o ma ion o assume ha one s a e is mo e p obable han ano he one (and, in his case, en opy educes o a ie y). Like a ie y, Hexp esses ou unce ain y o igno ance abou he sys em s a e. The ollowing esul , whe e we ob ain maximal ce ain y (o comple e in o ma ion) abou he s a e o he sys em, is s aigh o wa d. Lemma 1. The en opy anishes, i.e., H=0, i and only i he e exis s a s a e s∈Ssuch ha P(s)=1. As we ha e seen, he cons ain educes he unce ain y, ha is, he diffe ence be ween maximal and ac ual unce ain y. This diffe ence can also be in e p e ed in a diffe en way, as in o ma ion, and his o ically Hwas in oduced by Shannon [Shannon 48] as a measu e o he capaci y o in o ma ion ansmission o a communica ion channel. I we achie e in o ma ion abou he s a e o he sys em, hen his in o ma ion will educe ou unce ain y abou he sys em s a e, by excluding (o educing he p obabili y o ) a numbe o s a es. The in o ma ion, I, we ecei e om his achie emen is equal o he amoun o unce ain y ha is educed, ha is, he diffe ence be ween he p e ious knowledge abou he sys em and he la e one, I=Hbe o e −Ha e . Al hough Shannon disag eed wi h he use o he e m in o ma ion o desc ibe his measu e, his heo y came o be known as In o ma ion Theo y. Since hen, en opy has been used as a measu e o a numbe o highe -o de ela ional concep s, including complexi y and o ganiza ion, and i has been applied in se- e al knowledge fields (as biology, ecology, psychology, sociology, and economics) whe e he use o complex sys ems is una oidable. 3 Measu ing he En opy o P obabilis ic P Sys ems A his poin he e is no doub ha a p obabilis ic P sys em (no mind he way o define he p obabili y con olling he e olu ion o he sys em) can be a complex 561 Co don-F anco A., Sancho-Capa ini F.: A No e on Complexi y Measu es ... sys em wi h he possibili y o e ol e along he ime. Hence, all abo e pa ame e s can be applied o measu e he complexi y o his kind o sys ems. I espec i e which is he chosen possibili y o in oduce p obabili ies in a memb ane sys em (see [Ob ulowicz and P˘aun 03] o a de ailed s udy), i we look a he compu a ions he sys em gene a es, he esul is a ee wi h a p obabili y measu e o e i s nodes. Le us emembe ha o e a oo ed ee (an acyclic and connec ed g aph whe e a e ex is ema ked) we can define a di ec ela ion be ween adjacen nodes. Wi h espec o his ela ion, o e e y node xo he ee, we deno e by Ch(x) he se o i s child en ( ha could be emp y i xis a lea ) and we deno e by L he se o all he lea es o he ee. De ini ion 2. Gi en a oo ed ee G,wi h oo , we say ha a unc ion P: V(G)→[0,1] is a p obabili y unc ion o e Gi he ollowing condi ions a e e ified: –P( )=1, –∀x∈V(G)(P(x)>0), –∀x∈V(G)(x/∈L→y∈Ch(x)P(y)=1). De ini ion 3. Aweigh ed eeisapai (G, P), whe e Gis a oo ed ee and P is a p obabili y unc ion o e G. In his con ex , a p obabilis ic P sys em gene a es a oo ed ee wi h a p ob- abili y associa ed wi h he nodes labelled by configu a ions eachable in he compu a ion, whe e he oo o he ee is he ini ial configu a ion o he sys- em, and he p obabili y o e e y node is he p obabili y o each i om he p e ious configu a ion. This ee will be deno ed by T(Π) (o b iefly by T,i he e is no con usion). The se o maximal b anches o T( he compu a ions o he P sys em) will be deno ed by Comp(Π). I C∈Comp(Π), hen we deno e by Ci he i- h configu a ion o he compu a ion C, he e o e, C0is he ini ial con- figu a ion o he P sys em. We also deno e by |C| he leng h o he compu a ion C.(See[P´e ez-Jim´enez and Sancho-Capa ini 02] o a o mal defini ion o hese concep s.) De ini ion 4. A P obabilis ic P Sys em (PPS o sho ) is a pai , (Π,P), whe e Πis a P sys em (o any kind), and Pis a p obabili y unc ion o e T(Π). As a P sys em is a dynamic sys em whe e he p obabili y o diffe en e olu- ions depends on he ac ual s a e o he de ice, in o de o cap u e i s e olu ion, and o eflec i s ins an en opy, we p opose wo diffe en concep s o en opy, aglobal one and a dynamic one, espec i ely. 562 Co don-F anco A., Sancho-Capa ini F.: A No e on Complexi y Measu es ... In he case o he global en opy, we conside he se o possible compu a ions o he PPS as he s a e space, ha is, we s udy he diffe en inal s a es he P sys em can each in i s whole execu ion. To desc ibe he en opy o he global case, we need o de ine a p obabili y measu e o e Comp(Π). We achie e his by using he p obabili y defined o e he PPS: De ini ion 5. Gi en a PPS, (Π,P), we define a new p obabili y measu e o e Comp(Π), ha will be also deno ed by P, as ollows: P(C)=⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩  i≤|C| P(Ci),i Cis a hal ing compu a ion, lim n→|C|  i≤n P(Ci),o he wise. No e 6. Equi alen ly, P(C)=in {i≤nP(Ci): n≤|C|}.I iseasy ocheck ha he defini ion abo e is, in ac , a p obabili y measu e o e Comp(Π). Acco ding o he p e ious defini ion o en opy and he p obabili y defined in Comp(Π), he global en opy o he PPS is he ollowing one. De ini ion 7. The global en opy o a PPS, (Π,P), is defined as: Hg(Π)=− C∈ Comp(Π) P(C)·log(P(C)). No e 8. Since limx→0x·log(x) = 0, we conside 0 ·log(0) = 0. The global en opy measu es he unce ain y o he P sys em Π o e ol e along he possible compu a ions. No e ha , i he P sys em has only one possible compu a ion, C, henP(C) = 1, hence, om Lemma 1, he en opy o he sys em anishes; ha is, he e is no unce ain y abou he e olu ion o he sys em. Bu , is he e some way o define a measu e eflec ing he ins an aneous en- opy o he sys em? Nex , we will y o define a mo e complex measu e o he en opy o a PPS, whe e in some way he ins an o i s execu ion will be cap u ed. Bu , p e iously, we need some defini ions o e ees. In a oo ed ee, G, we can conside a dep h unc ion ecu si ely defined as ollows: dep(x)=0,i xis he oo o G, dep( (x)) + 1,o he wise, whe e, o e e y node xno being he oo , (x) s ands o he a he o xin G. 563 Co don-F anco A., Sancho-Capa ini F.: A No e on Complexi y Measu es ... The dep h o Gis defined as dep(G)=max x∈Gdep(x). Fo e e y n≤dep(G), we define he n-le el o Gas G|n={x∈G:dep(x)=n}, he lea es o Gas L={x∈G:Ch(x)=∅},Ln=L∩G|n,and Gn=G|n∪ k<n Lk. I x∈G, henwedeno ebyγx he se o all nodes belonging o he only pa h om he oo o x. I (G, P) is a ee wi h a p obabili y unc ion defined o e i s nodes, by using he pa hs defined abo e, we can define a new p obabili y unc ion (de i ed om P) o e he le els o G. Lemma 9. Le (G, P )be a weigh ed ee. Then, o e e y n∈N, he ollowing unc ion, Pn, is a p obabili y unc ion o e Gn: ∀x∈Gn,P n(x)=  y∈γx P(y). I (Π,P) is a PPS, hen Tis a oo ed ee, so we can apply all abo e defini- ions, ob aining he n-le el en opy o he sys em. De ini ion 10. Fo e e y n∈N, hen-le el en opy o a PPS, (Π,P), is defined as: Hn(Π)=− C∈Tn Pn(C)·log(Pn(C)). The sequence {Hn(Π)}n∈Nis called dynamic en opy. No e 11. The dynamic en opy gi es a measu e o he e olu ion o a PPS ha app oxima es he global en opy defined abo e, as i is shown in he nex lemma. Lemma 12. Fo e e y PPS, (Π,P), i holds ha {Hn(Π)}n∈Nis a mono onic non-dec easing sequence and lim n→∞ Hn(Π)=Hg(Π). Now we define he amoun o in o ma ion o he P sys em Πalong i s e o- lu ion. De ini ion 13. The sequence o in o ma ion o a PPS, (Π, P), is defined as: In(Π)=Hn(Π)−Hn+1(Π). 564 Co don-F anco A., Sancho-Capa ini F.: A No e on Complexi y Measu es ... Whe eas he global en opy defined abo e p o ides in o ma ion abou he global beha io o he sys em (wa ching all he possible compu a ions like a whole), he dynamic en opy p o ides an indica o abou i s local beha io , and, a p io i, no knowledge abou he diffe en e olu ion possibili ies is needed. Bu as a p ac ical ool o be used along he execu ion o a P obabilis ic P Sys em (whe e only one b anch o he ee is in execu ion), we p esen he condi ioned en opy, whe e only he ac ual s a e o he sys em is known. No e 14. I n∈N, hen we will deno e by Tn(C) he subse o Tnconsis ing o all he configu a ions o Tn ha can be eached om C. De ini ion 15. Le n, j be na u al numbe s such ha n≥j,le (Π,P)be a PPS, and C∈T.Then- h le el o en opy o Π, supposed ha Cis he con igu a ion o Πa he j- h s ep o he execu ion, is defined as : Hn(Π|Π(j)=C)=  C∈Tn(C) Pn(C) Pj(C)·log( Pn(C) Pj(C)). 4 Conclusions In his pape we ha e applied en opy measu es o Memb ane Compu ing in o de o gi e a new ool o ob aining in o ma ion abou he e olu ion o P ob- abilis ic P Sys ems (no mind he used a ian ). Only a fi s app oach o he applica ion o In o ma ion Theo y (a undamen al ool in he s udy o complex sys ems) o he s udy o Memb ane Compu ing has been p esen ed. We hink ha a deepe s udy o he desc ip i e complexi y (a bo h s uc u al and ope - a ional le els) o he de ices gene a ed in his model can be o a g ea alue. The in e p e a ion o P sys ems as complex sys ems, as well as hei demon- s a ed powe in he efficien esolu ion o ha d p oblems, sugges s a p omising di ec ion o he ep esen a ion o e y a ied complex sys ems ha , a he momen , lack an effec i e ma hema ical o maliza ion. In his way, some new ques ions a ise: is i possible o ep esen complex sys ems (in s uc u e and unc ion) wi hin his model? I so, can a P sys em be defined whe e some kind o eme gency (p ope ies no ini ially p esen in he sys em) a ises? Acknowledgmen The suppo o his esea ch h ough he p ojec TIC2002-04220-C03-01 o he Minis e io de Ciencia y Tecnolog´ıa o Spain, cofinanced by FEDER unds, is g a e ully acknowledged. 565 Co don-F anco A., Sancho-Capa ini F.: A No e on Complexi y Measu es ... Re e ences [Hall and Fagan 80] Hall A.D., Fagan R.E.: “Defini ion o a sys em”; “The Gene al Theo y o Sys ems Applied o Managemen and O ganiza ion” (D.M. Jamieson, G. Chen, L.L. Schkade, C.H. Smi h, eds.), In e sys ems Publica ions, Seaside CA (1980), 217–243 [Ob ulowicz and P˘aun 03] Ob ulowicz A., P˘aun Gh.: “(In sea ch o ) P obabilis ic P sys ems”; BioSys ems, 70, 2 (2003), 107–121 [P˘aun 00] P˘aun Gh.: “Compu ing wi h memb anes”; Jou nal o Compu e and Sys em Sciences, 61, 1 (2000), 108–143 [P´e ez-Jim´enez and Sancho-Capa ini 02] P´e ez-Jim´enez M.J., Sancho-Capa ini F.: “A o maliza ion o basic P sys ems”; Fundamen a In o ma icae, 49, 1–3 (2002), 261–272 [Shannon 48] Shannon C.E.: “A ma hema ical heo y o communica ion”; Bell Sys em Technical Jou nal, 27 (1948), 379–423 and 623–656 566 Co don-F anco A., Sancho-Capa ini F.: A No e on Complexi y Measu es ...