Gene al Topologies and P Sys ems
E zs´ebe Csuhaj-Va j´u1, Ma ian Gheo ghe2,3, and Mike S anne 2
1Depa men o Algo i hms and Thei Applica ions
Facul y o In o ma ics, E¨o ¨os Lo ´and Uni e si y,
P´azm´any P´e e s . 1/c, Budapes , 1117, Hunga y
[email p o ec ed]
2Depa men o Compu e Science, The Uni e si y o She ield
Regen Cou , 211 Po obello, She ield S1 4DP, Uni ed Kingdom
{M.S anne , M.Gheo ghe}@dcs.she .ac.uk
3Depa men o Compu e Science, Uni e si y o Pi e¸s i
S Ta gu din Vale, Pi e¸s i, Romania
Summa y. In his pape we in es iga e he use o gene al opological spaces as con ol
mechanisms o memb ane sys ems. Fo simplici y, we illus a e ou app oach by showing
how a bi a y opologies can be used o s udy he beha iou o memb ane sys ems wi h
ew i e and communica ion ules.
1 In oduc ion
Memb ane compu ing has eme ged in he las mo e han en yea s as a igo ous
esea ch ield as pa o na u al compu ing o uncon en ional compu ing. I is a
na u e-inspi ed compu a ional pa adigm including a la ge a ie y o models, called
memb ane sys ems, well-in es iga ed om a compu a ional pe spec i e, especially
wi h espec o hei compu a ional powe and complexi y aspec s [9]. A numbe
o p omising applica ions, mainly in biology, bu also in dis ibu ed compu ing,
linguis ics and g aphics [1], ha e been iden i ied and desc ibed.
The key ea u es o a memb ane sys em a e a se o compa men s (called e-
gions) delimi ed by memb anes,mul ise s o objec s con ained in hese egions,
ans o ma ion and communica ion ules desc ibing in e ac ions be ween objec s,
and a s a egy o e ol ing he sys em. This basic model is inspi ed by s anda d
models o he s uc u e and unc ions o a ypical euka yo ic cell, comp ising mul i-
ple compa men s con aining localised biochemical ma e ials and eac ions: a ious
chemical en i ies wi h di e en le els o complexi y eac unde speci ied ci cum-
s ances o p oduce new biochemicals suppo ing he cell’s li e and me abolism,
and hese may o may no be anspo ed o o he compa men s depending on
con ex . Many a ian s o memb ane sys em ha e been conside ed, some using
di e en ypes o biochemical agen and in e ac ion, o he s using a ious ypes o
s uc u al o ganisa ion o he compa men s and hei connec ions [9].
80 E. Csuhaj-Va ju, M. Gheo ghe, M. S anne
Memb ane sys ems in oduce in a e y na u al way a speci ic opology on he
sys em desc ibed, in which memb anes delimi compa men s con aining local ob-
jec s and in e ac ion ules, oge he wi h speci ic links be ween compa men s.
These links desc ibe communica ion channels allowing adjacen compa men s o
exchange chemicals. Al hough his opology is lexible enough o cope wi h he
challenge o modelling a ious na u al o enginee ing sys ems, he e a e cases
when a ine g ain opological s uc u e is equi ed. In a se ies o pape s, J.-L.
Gia i o and his collabo a o s ha e in es iga ed he use o opological ans o ma-
ions applied o a ious da a s uc u es, whe e algeb aic opology helps in de ining
he app op ia e da a se s selec ed o be ans o med [2]. The use o his app oach
o model a ious elemen s and ans o ma ions occu ing in memb ane compu -
ing has been in es iga ed in [4], while concep s ela ed o a spa ial compu ing
p og amming pa adigm, which pe mi he de ini ion and handling o a so o ge-
ome y, ha e been desc ibed in he con ex o he uncon en ional p og amming
language, MGS [7].
In his pape we in es iga e he use o opological spaces as con ol mechanisms
o memb ane sys ems. While he algeb aic opological app oach shows how he
memb ane s uc u e and i s basic ope a ions wi h mul ise s can be ep esen ed,
he e we use a opological space as a amewo k o con ol he e olu ion o he sys-
em wi h espec o a amily o open se s ha is associa ed wi h each compa men .
This app oach p oduces a ine g ain desc ip ion o local ope a ions occu ing in
each compa men by es ic ing he in e ac ions be ween objec s o hose om a
gi en neighbou hood. This ini ial s udy shows he in luence o an a bi a y opol-
ogy on he way basic memb ane sys ems compu e. In u u e wo k (c . Sec . 5)
we aim o in es iga e he ole o mo e speci ic opologies, hei impac on o he
ypes o memb ane sys em, and hei applica ions in sol ing/app oaching a ious
p oblems.
2 Basic no a ions and de ini ions
We b ie ly ecall basic no ions conce ning P sys ems. Fo mo e de ails on hese
sys ems and on P sys ems in gene al, we e e o [8, 9]. A basic e olu ion-
communica ion P sys em (P sys em o sho ) o deg ee nis a cons uc
Π= (O, µ, w1,...,wn, R1,...,Rn, i0)
whe e
1. Ois a ini e alphabe o symbols called objec s;
2. µis a memb ane s uc u e consis ing o nmemb anes ha a e labelled (in
a one-one manne ) wi h elemen s om a gi en alphabe A; hese memb anes
a e o ganised in a hie a chical way, like a ee, wi h he op memb ane ( oo )
called he skin memb ane, and he bo om ones (lea es) called elemen a y
memb anes;
Gene al Topologies and P Sys ems 81
3. o each 1 ≤i≤n,wi∈O∗is a mul ise o objec s associa ed wi h he egion
i( his is he egion delimi ed by memb ane i, bu no including he sub egions
delimi ed by i’s child en);
4. o each 1 ≤i≤n,Riis a ini e se o ules associa ed wi h he egion i,
o he o m u→( 1, a 1)...( m, a m), whe e u∈O+, j∈Oand a j∈
{in, ou , he e}(1 ≤j≤m); when a jis he e, we w i e simply jin place o
( j, a j);
5. i0is he label o an elemen a y memb ane o µ ha iden i ies he co esponding
ou pu egion.
A P sys em is in e p e ed dynamically as a compu a ional de ice comp ising a
se o nhie a chically nes ed memb anes ha iden i y ndis inc egions ( he mem-
b ane s uc u e µ), whe e each egion i= 1,...,n con ains a mul ise o objec s
(wi) and a ini e se o e olu ion ules (Ri) o he o m u→( 1, a 1)...( m, a m).
This ule emo es mul ise u om egion i, and hen adds each mul ise j
(1 ≤j≤m) o he mul ise o objec s in he co esponding a ge egion a j.
•I a jdoes no appea in he no a ion (by con en ion his occu s when he
a ge is he e), hen j emains in memb ane i;
•I a jis ou , hen jis sen o he pa en memb ane o i; i iis he skin
memb ane hen jis sen ou o he sys em;
•I a jis in, hen jis sen o one o he inne memb anes o i(i he e is mo e
han one child, he a ge is chosen non-de e minis ically);
•The in a ge can be eplaced by a p ecisely de ined des ina ion egion. I egion
kis a child o iand a jis k, hen jis sen o k.
A compu a ion o he sys em is ob ained by applying he a ailable ew i e ules
in a non-de e minis ic maximally pa allel manne 4, whe e each egion iini ially
con ains he co esponding ini e mul ise wi.
A compu a ion is conside ed success ul when i s a s om he ini ial con igu-
a ion and eaches a con igu a ion whe e no u he ules can be applied. I s esul ,
a na u al numbe , is ob ained by coun ing he objec s p esen in egion i0on com-
ple ion (o he ways o in e p e ing he esul o a P sys em compu a ion a e also
conside ed in he li e a u e [9]). Gi en he non-de e minis ic na u e o P sys em
compu a ion, di e en uns o a gi en sys em may gene a e di e en esul s. Fo
a gi en P sys em Π he se o numbe s ha can be compu ed is deno ed N(Π).
Recall ha ew i e ules a e o he o m u→( 1, a 1)...( m, a m), whe e
uis a mul ise . I in each o he ules in Π he mul ise ucon ains only a single
objec , hen Πis called a P sys em wi h non-coope a i e ules; o he wise i is a
P sys em wi h coope a i e ules. When a j=in he ule is said o ha e a bi a y
a ge , and when a j=ink o a speci ic egion k, i has a selec ed a ge .
4A simul aneous applica ion o ew i e ules is non-de e minis ic maximally pa allel
p o ided he applied ules a e chosen non-de e minis ically (possibly wi h epe i ion),
and he e a e insu icien esou ces o igge he simul aneous applica ion o any
addi ional ule.
82 E. Csuhaj-Va ju, M. Gheo ghe, M. S anne
2.1 Topological con en ions
Ou no a ion will gene ally ollow ha o [10]. Gi en any non-emp y se X, i s
powe se will be deno ed ℘X. We w i e ∅ o he emp y se . A opology on Xis
any subse o ℘X con aining bo h ∅and X, which is closed unde a bi a y unions
and ini e in e sec ions; he membe s o Ta e open (o T-open whe e ambigui y
migh o he wise a ise). The opology {∅, X}is he indisc e e opology on X; he
opology in which e e y single on {x} ∈ ℘X is open is he disc e e opology. An
open co e o A⊆Xis a subse o Twhose union con ains A.
The complemen o an open se is closed. The closu e A= ClsX(A) o a se
A⊆Xis he in e sec ion o all closed se s con aining A; i is he smalles such
se . The in e io A◦= In X(A) o Ais he union o all open se s con ained in A;
i is he la ges such se . The di e ence be ween he closu e and in e io o a se
is i s bounda y,∂A =A A◦.
Any opology Tcan also be ega ded as a pa ially o de ed se (pose ) o de ed
by se inclusion. I (Y, ≤) is a pose , an o de embedding o Yin Tis an injec ion
ı:Y→ T such ha y1≤y2i and only i ı(y1)≤ı(y2).
3 Con ol s uc u es
Fo he pu poses o his pape , a P sys em can be ega ded s uc u ally as a ee
whose nodes a e he memb anes, oge he wi h a unc ion mapping each node p
in Π o a co esponding mul ise o e A. This mul ise ells us how many copies
o each objec lie in he egion si ua ed be ween he memb ane and i s in e nal
sub-memb anes; see Fig. 1.
abbd
bb abb bcccb
aab abc
1
2 3 4
5 6
(a) ee
bb
aab
abc
bcccb
abb
abbd
4
12
3
5
6
(b) nes ed memb anes
Fig. 1. A gene ic P sys em s uc u e ep esen ed as (a) a ee; (b) a se o nes ed
memb anes.
In each memb ane and in any compu a ion s ep i is assumed ha all he
objec s p esen in he co esponding egion can eely in e ac acco ding o he
Gene al Topologies and P Sys ems 83
se o ules a ailable in ha egion. Maximal pa allelism also implies ha all he
objec s ha migh ake pa in a ious in e ac ions mus in e ac (each objec
akes pa in a mos one in e ac ion). While his scheme is easy o implemen , i
dis o s o some ex en he biological in ui ion ha in e ac ions a e local. I is no
enough ha wo chemicals a e p esen in a cell, hey mus also be loca ed close
o one ano he , bu he egions o a P sys em a e no inhe en ly associa ed wi h
any no ion o sepa a ion dis ance. We will he e o e o de -embed he memb anes
o he P sys em as open se s wi hin an essen ially a bi a y opology, and use
( ini e) open co e s o p o ide an indica ion o he dis ance be ween wo objec s.
We hen conside how he choice o opology a ec s he compu a ions ha can be
implemen ed.
In gene al he membe s o an open co e need no be disjoin . Region 4 o Fig.
1 con ains he mul ise bcccb. Figu e 2 illus a es a co e ing o his egion by h ee
open se s: A4,1,A4,2and A4,3. The open se A4,2con ains cc, and each o he
o he s con ains bc. Ini ially we only conside open co e s o egions; sub egions o
he enclosing memb ane will be equipped wi h co e s in hei own igh .
bb
aab
abc
bcccb
abb
abbd
4
12
3
5
6
(a) Nes ed memb anes ( egion 4
highligh ed)
A4,2
A4,3 A4,1
bc
b
c
c
(b) Open co e ing o egion 4
Fig. 2. Co e ing o egion 4 by open se s.
The opologically con olled compu a ion ha akes place wi h espec o hese
open se s is de ined as ollows: ules associa ed wi h memb ane ia e enabled i and
only i he e is a membe o he open co e which con ains all o he pa icipa ing
objec s. I any a ge o an enabled ule is he e, he associa ed p oduc s should
hen be placed back in o he same open se (i he ini ial objec s lie in mo e han
one membe o he co e , we choose one a andom and place he associa ed esul s
he e; hey need no be injec ed back in o he in e sec ion). O he wise i he a ge
is a (whe e a is assumed o ca y i s own open co e ), he ou pu will be placed
in an a bi a y membe o a ’s co e .

84 E. Csuhaj-Va ju, M. Gheo ghe, M. S anne
Despi e he in insically local na u e o con olled compu a ion, he locus o
compu a ion can mig a e om one compa men o ano he one ia non-emp y
o e lap egions, as he ollowing example illus a es. Figu e 3 shows he disjoin
pa s, B4,1–B4,7, o egion 4’s co e . These a e all o he o m U Vwhe e Uand V
a e open; o example B4,3= (A4,1∩A4,2∩A4,3) ∅, and B4,1=A4,1 (A4,2∪A4,3).
A4,2
A4,3 A4,1
bc
b
c
c
(a) Open co e
B4,5
B4,6
B4,7
B4,4
B4,3
B4,2 B4,1
(b) O e lap egions
A4,1 A4,2 A4,3
(c) Key o bounda ies
Fig. 3. The ini e co e ing o egion 4 and i s disjoin o e lap egions.
Suppose, hen, ha egion 4 has he ollowing ules associa ed wi h i :
1:bc →b; 2:bcc →c; 3:cc →c.
I we conside he sys em as a P sys em wi h no opological con ol in place, he
ollowing compu a ions can ake place:
1. bc c cb 1, 1
===⇒bcb 1
==⇒bb
2. bc cc b 1, 3
===⇒bcb 1
==⇒bb
3. bc ccb 1, 2
===⇒bc 1
==⇒b
Bu when he open se s a e in place compu a ion pa h 3 is blocked, because none
o he open se s e e con ains bcc, whence 2canno be igge ed. We ha e he
ollowing wo cases ins ead:
1’ 1is applied in bo h A4,1and A4,3 esul ing in a copy o bin each o hese
open se s; i b∈A4,3is no in A4,2∩A4,3 he compu a ion s ops he e wi h bbc
sca e ed ac oss di e en open se s. I , on he o he hand, b∈A4,2∩A4,3 hen
he compu a ion can con inue; a e applying 1in A4,2a copy o bis ob ained
in each o A4,1and A4,2. In his case he esul is he same as ha ob ained in
(1);
Gene al Topologies and P Sys ems 85
2’. 3, 1 esul in copies o b∈A4,1and c∈A4,2; as in (1’) his ccan eside ei he
in he in e sec ion o ou side i ; in he i s case 1can be applied again and b
is compu ed (so ha he esul om (2) is ob ained). O he wise bbc will emain
in he memb ane unchanged.
Conside in pa icula he second case o he i s s ep o (1’). A e 1is applied
in A4,3 he esul bcan be conside ed o lie in A4,2, whence (as sugges ed abo e)
he locus o compu a ion can mig a e om A4,3 o A4,2 ia hei in e sec ion. A
simila si ua ion occu s in (2’) as well.
Mo e gene ally, suppose ha egion ihas a ule whose a ge is egion j. We
will allow he ule o be igge ed only when he wo egions a e su icien ly close
o one ano he ( hei bounda ies mus in e sec : ∂i ∩∂j 6=∅). In his case, and
p o ided all o he equi ed componen s a e a ailable wi hin a single membe o
i’s co e , he ule can i e wi h he esul ing mul ise jbeing injec ed in o an
a bi a ily selec ed membe o j’s co e . In u u e wo k we plan o in es iga e
wha happens when his es ic ion is weakened, so ha in e ac ions can occu
be ween non-neighbou ing egions.
De ini ion 1 (Ou pu o a con olled compu a ion). Fo a P sys em Πand
associa ed opology T he se o numbe s compu ed by Πwhen con olled by Twill
be deno ed NT(Π).⊓⊔
Ha ing now de ined con olled compu a ion, we will add ess he ollowing p ob-
lems. In Sec . 4 we discuss he ole o a con ol mechanism based on an associa ed
opology and show how a gene al opology in luences he compu a ion o a basic
class o P sys ems. In Sec . 5 we summa ise ou indings and discuss u u e esea ch
opics ela ed o a ious opologies associa ed wi h classes o P sys ems.
4 Basic Resul s
We will i s conside P sys ems wi h non-coope a i e ules.
Lemma 1. Fo any P sys em wi h non-coope a i e ules and ei he a bi a y a -
ge s o selec ed a ge s, Π, and any associa ed opology T,N(Π) = NT(Π).
P oo . In a P sys em wi h non-coope a i e ules he le hand side o any ule has
only one single objec , hence no in e ac ions a e in ol ed. In his case i is ob ious
he he opology Tdoes no in luence he compu a ion o ei he P sys ems wi h
a bi a y a ge s o selec ed a ge s, hence he esul s a ed holds. ⊓⊔
Fo P sys ems wi h coope a i e ules he si ua ion is o ally di e en and he
opologies associa ed wi h hem may lead o di e en compu a ions and dis inc
esul s.
Lemma 2. The e is a P sys em wi h coope a i e ules and ei he a bi a y o
selec ed a ge s, Π, such ha o any associa ed opology Twhe e o a leas one
egion no all he objec s belong o he same open se , i ollows ha N(Π)6=
NT(Π).
86 E. Csuhaj-Va ju, M. Gheo ghe, M. S anne
P oo . Le us conside Π= (O, µ, w1, w2, R1, R2, i0), whe e O={a, b, c},µ=
[[]2]1,w1=ab,w2=λ,R1={ab →c, c →(c, in)},R2=∅,i0= 2. This sys em
uses an a bi a y a ge , which, in his case, is he same as selec ed a ge , in2.
This P sys em compu es cin wo s eps in he ou pu egion, 2. Any opology, T,
associa ed wi h Π ha p o ides a co e o egion 1 wi h mo e han an open se ,
mus ha e an open se o aand ano he one o band hei in e sec ion does no
con ain any o hese wo objec s; o he wise, aand bwill s ay in he same open
se . In his case he ule ab →ccan no be applied and consequen ly cis ne e
ob ained in he ou pu egion, hence N(Π)6=NT(Π). ⊓⊔
Theo em 1. Fo any P sys em wi h ei he a bi a y o selec ed a ge s, he com-
pu a ion and he opologically con olled compu a ion a e he same when non-
coope a i e ules a e used and a e no in gene al he same o coope a i e ules.
P oo . The p oo is an immedia e consequence o Lemmas 1 and 2. ⊓⊔
The e a e P sys ems wi h coope a i e ules whe e he con en o he egions can
be ma ched agains he open se s in such a way ha he compu a ion is equi alen
o he compu a ion o he o iginal sys em. Indeed le us conside he p oblem o
checking ha a posi i e in ege mis di ided by ano he posi i e in ege k. We
p opose a P sys em below which is an adap a ion o he P sys em p esen ed in [9].
Example 1. Le us conside Π= (O, µ, w1, w2, R1, R2, i0), whe e O={a, b, c, y, n},
µ= [[]2]1,w1=ambk,w2=y,R1={ 1:ab →c, 2:ac →b, 3:bc →(n, in)},
R2={yn →n},i0= 2.
In he i s s ep a mos kobjec s ab a e eplaced by he same numbe o objec s
c(using 1a mos k imes) and hen objec s ac a e eplaced by objec s b(using
2). I kdi ides m hen he p ocess will s op a e hs eps, whe e m=kh, and in
memb ane 2 will emain y; o he wise in memb ane 1 he p ocess o al e na i ely
applying ules 1and 2will s op wi h some objec s band objec s cand he ule
3can be used. In his case nis sen in o egion 2 and inally nis ob ained in his
egion.
Now, i we aim o ob ain he same esul s in egion 2, i.e., y, when kdi ides
m, o no he wise, hen we ha e o build he opology, T, associa ed wi h Πin a
ce ain way which is subsequen ly desc ibed. Region 2 is co e ed by only one single
open se and egion 1 will ha e an a bi a y numbe o open se s, q > 1, associa ed
wi h. Any wo such open se s a e disjoin . The objec s will be dis ibu ed as ollows:
he k b′s will be andomly dis ibu ed in q−1 o he qopen se s, bk1,...,bkq−1,
ki≥0 and k1+· · · +kq−1=k. I m=kh + , hen in each o he q−1 open
se s con aining kib′s, he numbe o a′s is hkia′s. I > 0 hen one mo e awill
be conside in one o he q−1 open se s wi h b′s and he es will be associa ed
wi h he q h open se . Clea ly, in each o he q−1 open se s he compu a ion will
go o hs eps. In q−2 o hem i will be ob ained ei he only b′s o only c′s; he
open se wi h an addi ional ain i will end up a e one mo e s ep wi h a mix u e
o b′s and c′s and he ule 3will push an nin o memb ane 2 and inally will ge
nin his memb ane. Objec s a′s occu ing in he q h open se will emain he e
o e e . I ollows ha N(Π) = NT(Π). ⊓⊔
Gene al Topologies and P Sys ems 87
The ques ion o whe he he con ol s uc u e in oduced by a opology can be
igno ed, pe haps by using a mo e complex P sys em, is answe ed by he ollowing
esul . This akes in o accoun he in e p e a ion o he ou come o he compu a-
ion as being he numbe o objec s, gi en by he size o he mul ise , p esen in
he ou pu egion.
Theo em 2. Fo any P sys em, Π, and any associa ed opology, T, he e is a P
sys em, Π′, o he same deg ee wi h Π, such ha NT(Π) = N(Π′).
P oo . The idea o he p oo is o cons uc a new P sys em such ha objec s be-
longing o a egion adequa ely e e o objec s o he open se s in he co esponding
egions o he ini ial P sys em.
Le Πbe a P sys em o deg ee n,Π= (O, µ, w1,...,wn, R1, . . . , Rn, i0), and
Ta opology associa ed wi h i . In o de o build a new P sys em, Π′, o deg ee n,
a ew p elimina y no a ions a e made. Fi s , please obse e ha o each egion i,
1≤i≤n, he e exis s a amily o open se s Ai,1,...,Ai,kico e ing i . In gene al
hese open se s a e no disjoin and we desc ibe he ines disjoin pa s o he co e
by conside ing ei he some in e sec ions o open se s o he complemen o an open
se wi h espec o he es o he open se s; i ollows ha he e exis s a ini e
se , deno ed Bi, con aining he se s Bi,1,...,Bi,mi, such ha Bi,j deno es ei he
Ai,l1∩· · ·∩Ai,lj, 1 ≤lj≤kio Ai,j (Ai,1∪ · · ·∪Ai,j−1∪Ai,j+1 ∪ · · ·∪Ai,ki). The
se o indexes o he abo e se s Bi,j is deno ed by Ci, i.e., Ci={(i, j)|Bi,j ∈Bi}.
Each objec , a∈O, o he mul ise om egion ibelongs o a ce ain Bi,j. Fo
each a om Bi,j, he ollowing objec s a e conside ed, aα, α ∈Ci.
The P sys em Π′, o deg ee n, is buil as ollows:
Π′= (O′, µ, w′
1,...,w′
n, R′
1,...,R′
ni0),
whe e:
1. O′={aα|a∈O, α ∈Ci,1≤i≤n};
2. µis he memb ane s uc u e o Π;
3. w′
i=a(i, 1)
i,1. . . a(i, pi)
i,pi, whe e ai,j ∈Bi, j, 1 ≤j≤pi, o wi=ai,1. . . ai,pi,
ini ial mul ise o Π;
4. o each ule ai,1. . . ai,qi→bi,1. . . bi,si∈Ri,R′
icon ains a(i, 1)
i,1. . . a(i, qi)
i,qi→
b(i,s1)
i,1. . . b(i,spi)
i,pi, (i, j)∈Ci,1≤j≤qi, (i, sj)∈Ci, 1 ≤j≤piwhen a a ge ,
, appea s on he igh hand side o he ule om Ri, associa ed wi h an objec
bi,j, hen he a ge will poin o any o he open se s A ,j o he a ge egion
;
5. Πand Π′ha e he same ou pu memb ane, i0.
The codi ica ion p o ided by Π′alloca es, in a unique way, in e e y egion,
i, each objec , a, o a speci ic open se , by “s amping” i wi h he co esponding
index, (i, j)∈Ci, o he se Bi,j. Whene e a ule is applied, he esul ed mul ise
is also composed o objec s uniquely associa ed wi h ce ain open se s, ei he om
he cu en egion o om he a ge ones.