EP-colonies: Mic o–O ganisms in a Cell-like
En i onmen
E zs´ebe Csuhaj-Va j´u
Compu e and Au oma ion Ins i u e
Hunga ian Academy o Sciences
Kende u ca 13–17, H-1111 Budapes , Hunga y
E-mail: [email p o ec ed]
Summa y. The aim o his no e is o in oduce a model o desc ibing popula ions
o ex emely simple o ganisms which li e in and in e ac wi h a dynamically changing
cell-like en i onmen . In addi ion o he de ini ion o he no ion, we p esen examples
illus a ing some possible p ope ies o hese cons uc s and p opose some bio-inspi ed
p oblems o s udy.
1 In oduc ion
P sys ems o memb ane sys ems a e uncon en ional models o compu ing, in mos
cases as powe ul as he Tu ing machines. The no ion – abs ac ed om he s uc-
u e and he unc ioning o he li ing cell – was in oduced by Gh. P˘aun [4]. A P
sys em is a memb ane a chi ec u e which sepa a es egions con aining mul ise s
o objec s. These objec s co espond o chemicals (chemical ing edien s), which
– ep esen ing chemical eac ions – migh change and mo e among he di e en
egions, acco ding o ules associa ed o he egions. As he eade migh ob-
se e, a P sys em is a a he complex objec , and his is why i is sui able bo h
o compu ing and modelling biological o bio-chemical phenomena. The model,
whe e he P sys em communica es wi h an en i onmen h ough inpu and ou pu
objec s, is called P au oma on [2]. Ce ain a ian s o P au oma a a e compu a-
ionally comple e, mo eo e i can be shown ha collec ions o ex emely simple
P au oma a-like cons uc s can also o m compu a ional de ices o he powe o
he Tu ing machines. Such cons uc s a e he so-called P colonies [3], a class o ab-
s ac de ices composed om as simple as possible P au oma a-like sys ems ac ing
and e ol ing in a sha ed en i onmen . The membe s o he P colony, he cells, a e
ep esen ed by a bounded numbe o objec s (and his numbe does no change
du ing he compu a ion) and a ini e numbe o p og ams which a e uples o ules
o he o m a→bo c−→ d, whe e a, b, c, d a e objec s. The ule a→bmeans
ha an objec ain he cell is changed o an objec b, i.e., he chemical changes
acco ding o ules o a chemical eac ion. The ule c−→ dmeans ha an objec
124 E. Csuhaj–Va j´u
c ound inside he cell is exchanged wi h an objec d ound ou side, in he en i-
onmen , ha is, dis inpu he cell and cis ou pu . The la e ule desc ibes he
communica ion be ween he cell and i s en i onmen and each p og am con ains
only one communica ion ule. The cells a e able o sc u inize hei en i onmen ,
ha is, o obse e he p esence o absence o a ce ain objec . The cell unc ions
by changing i s s a es which is ealized by pe o ming one o i s p og ams. The
applica ion o a p og am means a pa allel applica ion o a ule o each objec in
he cell. A P colony unc ions in such manne ha a any momen o ime each
enabled cell changes i s s a es. Those cells which a e no able o pe o m a p og am
emain inac i e. Bo h a he beginning and du ing he whole unc ioning o he
sys em he en i onmen is supposed o be an in ini e supply o a special objec ,
called he en i onmen al objec . A e s a ing, he e olu ion o he collec ion o
he cells, he P colony, con inues as long as no cell can be ound which is able o
apply any o i s p og ams. In his case we say ha he compu a ion hal s. The
esul o a hal ing compu a ion is he numbe o copies o a dis inguished objec
p esen in he en i onmen . I is easy o obse e ha he ole o he en i onmen is
essen ial in hese cons uc s, i is a medium bo h o communica ion and o s o -
ing an unbounded quan i y o in o ma ion. In [3] i was shown ha P colonies a e
as powe ul as he Tu ing machines. The la ge compu a ional powe o P colonies
is due o bo h hese ea u es o he en i onmen and he capabili y o he cells o
check he p esence o he objec s in he en i onmen .
One na u al idea which immedia ely eme ges examining he concep o P
colonies is he ollowing: Wha abou cons uc s whe e he en i onmen is bounded
bu dynamically changing no only due o he ac ions o he cells bu o i s own
ules as well? Fo example, wha abou P colonies whe e he ac ual objec s in he
en i onmen a e gene a ed in some manne ? Con inuing his line o ideas, wha
abou cons uc s, whe e he s uc u ed en i onmen is a P sys em and he egions
migh con ain usual objec s, which co espond o chemicals, and o he objec s
which co espond o cells in a P colony? These la e cons uc s can be conside ed
as models o cells wi h e y simple mic o-o ganisms inside he egions. How hese
mic o-o ganisms in luence he beha io o he cell? Wha can we say abou hese
sys ems bo h om compu a ional poin o iew and om he poin o iew o mod-
elling biological phenomena? We no e ha his model is a ela ed concep o he
so-called eco-g amma sys em [1], a o mal language heo e ic model o a collec ion
o agen s which a e in in e ac ion wi h hei dynamically changing en i onmen .
The heo y o eco-g amma sys ems o ms a sub ield o g amma sys ems heo y,
an a ea in o mal language heo y p o iding models o desc ibing mul i-agen
sys ems.
In his no e, we in oduce he new model, called EP colony, whe e le e E
e e s bo h o e olu ion and en i onmen , and hen we illus a e he no ion by
some e y simple examples. A he same ime, we p opose opics, inspi ed by
biological phenomena, o u u e esea ch.
EP-colonies: Mic o–O ganisms in a Cell-like En i onmen 125
2 The Concep
We suppose ha he eade is amilia wi h he basic elemen s o o mal languages,
hus we in oduce he e in a o mal way only ou compu ing model and p esen a
ew basic no ions.
An alphabe is a ini e and non-emp y se o abs ac symbols. Fo an alphabe
Awe deno e by A∗ he se o all s ings o symbols om A, including he emp y
s ing. A mul ise o e an alphabe Ais a mapping om A o N, he se o na u al
numbe s; we ep esen a mul ise by a s ing om A∗( he numbe o occu ences
o a symbol a∈Ain a s ing w ep esen s he mul iplici y o ain he mul ise
ep esen ed by w; hus, all s ings ob ained by pe mu ing symbols in he s ing w
ep esen he same mul ise ).
We p esen he basic no ions o memb ane compu ing; he in e es ed eade
may ind mo e de ailed in o ma ion on he heo y o P sys ems in he mono-
g aph [5]. A P sys em is a s uc u e o hie a chically embedded memb anes, each
ha ing a label and enclosing a egion con aining a mul ise o objec s and pos-
sibly o he memb anes. The ou -mos memb ane which is unique and usually
labelled wi h 1, is called he skin memb ane. The memb ane s uc u e is ep-
esen ed by a sequence o ma ching pa en heses whe e he ma ching pai s ha e
he same label as he memb anes hey ep esen . I x∈ {[i,]i|1≤i≤n}∗is
such a s ing o ma ching pa en heses o leng h 2n, deno ing a s uc u e whe e
memb ane icon ains memb ane j, hen x=x1[ix2[jx3]jx4]ix5 o some
xk∈ {[l,]l|1≤l≤n, l 6=i, j}∗,1≤k≤5. I memb ane icon ains memb ane
j, and he e is no o he memb ane, k, such ha kcon ains jand icon ains k(x2
and x4abo e a e s ings o ma ching pa en heses hemsel es), hen we say ha
memb ane iis he pa en memb ane o j, deno ed by i=pa en (j), and a he
same ime, memb ane jis one o he child memb anes o i.
By he con en s o a egion we mean he mul ise o objec s which is con ained
by he co esponding memb ane excluding hose objec s which a e con ained by
any o i s child memb anes.
Now we in oduce he compu ing de ice we conside in his pape .
De ini ion 1. An EP colony is a cons uc
Π= (VE, VA, µ, R1, . . . , Rn, C1, . . . , Cs, w1, . . . , wn), n ≥1, s ≥1,
whe e:
•VEis an alphabe , he alphabe o en i onmen al objec s in Π;
•VA={C1, . . . , Cs} ∪ {(,)}, whe e {C1, . . . , Cs}is he alphabe o he names o
he mic o-o ganisms ( he ypes o he mic o-o ganisms) in Π, and symbols (
and )a e sepa a o s; VEand VAa e disjoin alphabe s.
•µis a memb ane s uc u e wi h nmemb anes;
126 E. Csuhaj–Va j´u
•Ri,1≤i≤n, is he se o ules o he i- h egion (memb ane); each ule
is o he o m u→ ( a ),whe e uand a e mul ise s o e VEand a ∈
{he e, in, ou };
•Cj= (Oj, Pj),1≤j≤s, is a mic o-o ganism, whe e
–Ojis a ini e mul ise o e VE( he ini ial s a e o he mic o-o ganism), and
–Pjis a ini e se {pj,1, . . . , pj,kj},kj≥1,o p og ams.
Each p og am pj,l is an sj,l- uple o ules o he o m ( j,l,1, . . . , j,l,sj,l ),
sj,l ≥1, wi h sj,l =ca d(Qj),whe e j,l,1is o he o m c−→ d(one objec
exchange wi h he en i onmen ), and ules j,l,2, . . . , j,l,sj,l a e o he o m
a→b(e olu ion ule). Objec s a, b, c, d a e elemen s o (VE∪VA)− {(,)}.
•wiis he ini ial con en s (mul ise ) o he i- h memb ane, wi h wi=
(Oi1). . . (Oisi),whe e is a mul ise o objec s o e VEand Oik, o 1≤
k≤si,a e ini ial s a es o mic o-o ganisms.
The ini ial s a e o Πis he n- uple (w1, . . . , wn),whe e wi,1≤i≤n, is he
ini ial s a e o egion i.
We de ine he s a e o he EP colony in an analogous manne . I is an n- uple
(u1, . . . , un), whe e uiis he s a e o he i- h egion and ui= (Hi1)...(Hi i),
i≥0,whe e is a mul ise o objec s om VEand Hik,1≤k≤ iis a mul ise
o objec s o e (VE∪VA)− {(,)}, he s a e o a mic o-o ganism ound in egion
i. We no e ha he numbe o he mic o-o ganisms ound in a egion can change
unde he unc ioning.
No ice ha any mic o-o ganism can be conside ed as a small P sys em wi h
only one memb ane; we use he sepa a o symbols ( and ) only o echnical easons.
Thus, he egions o he EP colony migh con ain wo ypes o objec s: i s ly,
usual chemicals, ep esen ed by elemen s o VE.Mul ise s o hese objec s migh
unde go chemical eac ions, desc ibed by he ules u→ ( a ).In his case, a
mul ise o objec s uchanges o a mul ise o objec s and hen ei he emains
in he egion ( a =he e), o lea es he egion in some di ec ion ( a =in o
a =ou ). These ules co espond o s anda d ules o P sys ems. Secondly, he e
migh be mic o-o ganisms in he egion, which can change hei s a es. Unde a
change o hei s a e, hese mic o-o ganisms pe o m a ule o any objec hey
ha e. When hey apply he communica ion ule, hen hey exchange an objec
( his can be he same objec ) wi h hei en i onmen which is now he con en s
o he egion. When hey pe o m an e olu ion ule, hen hey ew i e (possibly
iden ically) an objec hey ha e. No ice an impo an poin in he de ini ion: he
ules o he mic o-o ganism a e allowed o manipula e (c ea e, dele e, exchange)
mic o-o ganisms as ollows: i a communica ion ule a−→ Cis used, whe e Cis a
le e om VA, ha is, he name o a mic o-o ganism, hen a new mic o-o ganism
ge s bi h in he egion (wi h he ini ial con en s o i s ype); i a communica ion
ule C−→ ais used, whe e Cis a le e om VA, hen a mic o-o ganism o
ype Cdisappea s ( empo a ily) om he egion. A ule a→Cwi h Cas abo e
and a∈VEindica es he po en ial bi h o a mic o-o ganism in ano he mic o-
o ganism, while a ule C→a e e s o ha he mic o-o ganism is ex inc , and
EP-colonies: Mic o–O ganisms in a Cell-like En i onmen 127
he ule C1→C2wi h C1, C2∈VAmeans ha he ype o he po en ial mic o-
o ganism is changed. Thus, he ules make possible o change he numbe o he
mic o-o ganisms in he egions.
A e his explana ion we de ine he way o he unc ioning o EP colonies. Since
he o mal de ails a e a he complica ed, we p esen an in o mal explana ion.
The EP sys em Π unc ions by changing i s s a es as ollows: a e e y di ec
change o he s a e each enabled mic o-o ganism (a maximal numbe o enabled
mic o-o ganisms) in any egion mus pe o m one o i s p og ams. In he i s case
he mic o-o ganisms unc ion in a so-called s ongly compe i i e manne , while in
he second case hey wo k in a weakly compe i i e manne . The mic o-o ganism
is called enabled i i is able o pe o m one o i s p og ams. In he case o s ong
compe i ion, i he e is no su icien en i onmen al symbol o mic o-o ganism in he
egion o p ocess o e e y enabled mic o-o ganism, hen he sys em is blocked. In
he case o weak compe i ion, hose mic o-o ganisms which a e no able o pe o m
a p og am emain inac i e and hen hey ei he emain in he egion o lea e he
egion in some di ec ion, chosen non-de e minis ically. The en i onmen al objec s
in he egion which we e no a ec ed by he mic o-o ganisms a e de eloped and
communica ed by applying he ules o he co esponding egion. These ules a e
applied in a maximal pa allel manne , ha is, as many ules a e applied in pa allel
as i is possible: i a ule can be applied in he en i onmen , hen i mus be applied.
The sequences o di ec changes o he s a e de ine he compu a ions in he
EP sys em. We can de ine he esul o he compu a ion h ough he concep o
hal ing and hus by a hal ing s a e. Hal ing can be conside ed in di e en manne s:
One possibili y is, o example, when he e is no mic o-o ganism o pe o m any
p og am in any o he egions. The second (s onge ) condi ion is: i no ac ion is
possible o be pe o med in he sys ems, i.e., he e is no enabled mic o-o ganism
and no enabled ule in any egion. (A ule o a egion is enabled i i can be
pe o med.)
While he abo e a ian s de ine he esul o he compu a ion by hal ing, we can
de ine i h ough equilib ium as well, ha is, as s a es which change o hemsel es.
3 Topics o Resea ch
EP colonies as P colonies a e a he complex cons uc s, bo h in hei s uc u e
and hei unc ioning, hus hei la ge compu a ional powe is expec ed. In [3],
he compu a ional comple eness o P colonies was p o ed, by di e en simula ions
o egis e machines (which is known o be o uni e sal powe ). To ob ain his
la ge compu a ional powe , a any s ep o he compu a ion a ce ain bu bounded
numbe o new copies o he so-called special en i onmen al symbol was used.
(Remembe ha he en i onmen in his case con ains an in ini e numbe o copies
o his symbol). Using some i ial gene a i e ules and a special new so-called
ma ke symbol, we can easily p oduce his amoun o en i onmen al symbols a
each s ep. Thus, i is easy o demons a e ha EP colonies, e en wi h one egion

128 E. Csuhaj–Va j´u
and wi h a limi ed numbe o mic o-o ganisms (and his numbe does no change
unde unc ioning) a e as powe ul as he egis e machines. The e o e, i we would
like o s udy EP colonies om he poin o iew o compu a ion, we should ind
na u al and easonable es ic ions o he model.
Howe e , one in e es ing p oblem o s udy is, whe he o no he wo di e en
unc ioning modes a e equi alen . Namely, o decide whe he o no he s ong
compe i ion and he weak compe i ion lead o di e en compu a ional powe s,
and which a e he es ic ions o he model ha imply di e ence. The answe o
his ques ion can also be ela ed o he ollowing p oblem. How long a mic o-
o ganism can emain ali e, can esis in an inac i e s a e? Supposing ha inac i e
s a es a e possible, has his ac any in luence on he beha io o he sys em?
The ollowing simple example demons a es some di e ences be ween he wo
unc ioning modes.
Example 1. Ins ead o he o mal de ails, we desc ibe he EP colony in an in o mal
manne . Suppose ha i has one memb ane and h ee iden ical mic o-o ganisms.
The ules o he memb ane a e a→a,a→b, b →a, b →b, and he p og am o
he mic o-o ganisms is (a↔b, b →a), and hey ha e ab as ini ial s a e. Assume
he EP colony ha ing he ini ial s a e (b6(ab)(ab)(ab)).In he case o s ongly
compe i i e unc ioning he EP colony is able o wo k i and only i a any s ep o
he unc ioning a leas 3 copies o objec ba e p esen in he en i onmen ; i his
is no he case, hen he unc ioning o he EP colony ge s blocked. In he case
o he weak compe i ion among he mic o-o ganisms, he sys em can con inue i s
wo k o any numbe o occu ences o b.
While in he case o P colonies he esea ch emphasis was pu on he compu a-
ional powe o he sys em, in o de o demons a e ha e y simple compu a ional
de ices wi h indi ec communica ion can be o la ge compu a ional powe , in he
case o EP colonies he p ope ies o hei s a e sequences a e in he ocus o in e -
es : o example, can we de ec pe iodici y wi h espec o some p ope ies in he
s a e sequence o he EP sys em is wi h ape iodic beha io in ce ain p ope ies.
Fo example, is he e some pe iodici y in he numbe o mic o-o ganisms o in he
numbe o mic o-o ganisms o he same ype occu ing in a ce ain egion du ing
he unc ioning o he sys em? O , i we associa e pa e ns o he popula ion o he
mic o-o ganisms, can we iden i y some well-known pa e ns unde he unc ioning?
EP sys ems p o ide he possibili y o de ining uncon en ional complexi y mea-
su es. Fo example, in he case o weak compe i i e unc ioning, impo an mea-
su es can be he so-called mig a ion complexi y measu es: he numbe o mic o-
o ganisms lea ing he egion whe e hey a e p esen ( hese mic o-o ganisms mi-
g a e om one egion in o ano he one), he numbe o mic o-o ganisms lea ing
a ce ain egion a a change o a s a e o in he cou se o he unc ioning, e c.
Analogously, we can examine hese pa ame e s wi h espec o a ce ain ype o
mic o-o ganisms. In e es ing ques ions a e, wha abou EP sys ems wi h cons an ,
linea ly bounded, o polynomially bounded mig a ion complexi ies?
The ollowing simple example demons a es he beha io o an EP colony unde
mig a ion.
EP-colonies: Mic o–O ganisms in a Cell-like En i onmen 129
Example 2. As in he p e ious case, we p esen only he necessa y o malism. Le
he EP colony ha e wo memb anes, namely he memb ane s uc u e [[ ]2]1, and
one mic o-o ganism. Le he ules o he egions be de ined as ollows: egion 1:
a→a,a0→a00a00, a00 →aand egion 2: d→d2, c →c.
Le he mic o-o ganism ha e he ollowing p og ams:
•(a0↔a, a →a0, c →c),
•(c↔d, a0→a00, a →a),
•(a00 ↔a, a0→a00, d →d),
•(d↔c, a00 →a0, a →a).
Suppose ha he mic o-o ganism s a s wo king om he ini ial s a e a0ac
and le he EP colony has he ini ial s a e (a(a0ac), d).(The mic o-o ganism is
in egion 1.) Mo eo e , suppose ha when he mic o-o ganism has no applicable
p og am in he egion, hen i mo es o he o he egion.
Then, o any k, he e a e pe iods o he compu a ion o leng h 2ksuch ha
he mic o-o ganism does no lea e he i s egion du ing his pe iod.
Simila ly o he mig a ion complexi y, o he in e es ing complexi y measu es
can be he so-called in ec ion size and he so-called in ec ion le el o he EP colony.
The size o he in ec ion o a egion (o he EP colony) is he numbe o mic o-
o ganisms ound in he egion (in he sys em); while he in ec ion le el is he
numbe o he mic o-o ganisms di ided by he numbe o en i onmen al objec s
o by he o al numbe o objec s in he egion (o in he sys em). No ice ha
hese measu es a e o pa icula in e es , hey migh make i possible o de ine
he no ion o an epidemic, i.e., an inc easing numbe o mic o-o ganisms unde
unc ioning, o esis ance, i.e., an (almos ) cons an numbe o mic o-o ganisms
du ing he whole compu a ion.
We illus a e hese no ions by a simple example.
Example 3. Ins ead o he o mal de ails, we gi e he example in a a he in o mal
way. Suppose ha he EP colony has one memb ane and kmic o-o ganisms. Le
he egion ha e he ollowing ules: a→a2,bi→a2, 1 ≤i≤k.
Le mic o-o ganism Ci,1≤i≤k, be gi en wi h he ollowing p og am: (a↔
bi, a →bi), and le i s ini ial s a e abi.
Suppose ha he ini ial s a e o he EP colony is a2k+1(ab1). . . (abk).
Then, a any momen o ime, objec s bi,1≤i≤k, a e p esen in he egion
and he numbe o copies o objec ais exponen ially inc easing. The in ec ion size
is cons an and he in ec ion le el con e ges o he ze o.
EP colonies o e a wide a ie y o p oblems o s udy. The model is su icien ly
complex no only o compu ing bu ealizing in e es ing beha io al pa e ns as
well. Especially in e es ing candida es o u u e esea ch a e he ex ensions o
he models de ined o e wo-dimensional o h ee-dimensional objec s. These and
simila ques ions a e wai ing o in es iga ion.
130 E. Csuhaj–Va j´u
Re e ences
1. E. Csuhaj-Va j´u, A. Kelemeno ´a, J. Kelemen, Gh. P˘aun: Eco-g amma sys ems – A
g amma ical amewo k o li e-like in e ac ions. A i icial Li e, 3 (1997), 1–28.
2. E. Csuhaj-Va j´u, Gy. Vaszil: P au oma a. In P e-P oceedings o he Wo kshop on
Memb ane Compu ing WMC-CdeA 2002 (Gh. P˘aun, C. Zand on, eds.), Cu ea de
A ge¸s, Romania, Augus 19-23, 2002. Pub. No. 1 o MolCoNe -IST-2001-32008 (2002)
177–192, and also in Memb ane Compu ing. Lec u e No es in Compu e Science (Gh.
P˘aun, G. Rozenbe g, A. Salomaa, C. Zand on, eds.), LNCS 2597, Sp inge -Ve lag,
Be lin, 2003, 219–233.
3. J. Kelemen, A. Kelemeno ´a, Gh. P˘aun: P e iew o P colonies: A biochemically in-
spi ed compu ing model. In: Wo kshop and Tu o ial P oceedings. Nin h In e na ional
Con e ence on he Simula ion and Syn hesis o Li ing Sys ems (Ali e IX) (M. Bedau
e al., eds.), Bos on Mass., 2004, 82–86.
4. Gh. P˘aun: Compu ing wi h memb anes. Jou nal o Compu e and Sys em Sciences,
61 (2000), 108–143.
5. Gh. P˘aun: Memb ane Compu ing. An In oduc ion. Sp inge -Ve lag, Be lin, 2002.