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