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 ...