P Sys ems wi h Endosomes
Robe o Ba bu i, Giulio Ca a agna, And ea Maggiolo–Sche ini, Paolo Milazzo
Dipa imen o di In o ma ica, Uni e si `a di Pisa
La go Pon eco o 3, 56127 Pisa, I aly.
{ba bu i,ca a agn,maggiolo,milazzo}@di.unipi.i
Summa y. P Sys ems a e compu ing de ices inspi ed by he s uc u e and he unc-
ioning o a li ing cell. A P Sys em consis s o a hie a chy o memb anes, each o hem
con aining a mul ise o objec s, a se o e olu ion ules, and possibly o he memb anes.
E olu ion ules a e applied o he objec s o he same memb ane wi h maximal pa -
allelism. In his pape we p esen an ex ension o P Sys ems, called P Sys ems wi h
Endosomes (PE Sys ems), in which endosomes can be explici ly modeled. We show ha
PE Sys ems a e uni e sal e en i only he simples o m o e olu ion ules is conside ed,
and we gi e one applica ion examples.
1 In oduc ion
P Sys ems we e in oduced by Pˇaun in [10] as dis ibu ed pa allel compu ing
de ices inspi ed by he s uc u e and he unc ioning o a li ing cell. A P Sys em
consis s o a hie a chy o memb anes, each o hem con aining a mul ise o objec s,
ep esen ing molecules, a se o e olu ion ules, ep esen ing chemical eac ions,
and possibly o he memb anes. Fo each e olu ion ule he e a e wo mul ise s
o objec s, desc ibing he eac an s and he p oduc s o he chemical eac ion. A
ule in a memb ane can be applied only o objec s in he same memb ane. Some
objec s p oduced by he ule emain in he same memb ane, o he s a e sen ou o
he memb ane, o he s a e sen in o he inne memb anes, which a e iden i ied by
hei labels. E olu ion ules a e applied wi h maximal pa allelism, meaning ha
i canno happen ha some e olu ion ule is no applied when he objec s needed
o i s igge ing a e a ailable.
Many a ian s and ex ensions o P Sys ems exis ha include ea u es o in-
c ease hei exp essi eness and ha a e based on di e en e olu ion s a egies.
Among he mos common ex ensions we men ion P Sys ems wi h dissolu ion ules
ha allow a memb ane o disappea and elease in he en i onmen all he ob-
jec s i con ains. We men ion also P Sys ems wi h p io i ies, in which a p io i y
ela ionship exis s among he e olu ion ules o each memb ane and can in luence
he applicabili y o such ules, and P Sys ems wi h p omo e s and inhibi o s, in
52 R. Ba bu i e al.
which he applicabili y o e olu ion ules depends on he p esence o a leas one
occu ence and on he absence, espec i ely, o a speci ic objec . See [2, 11] o he
de ini ion o hese (and o he ) a ian s o P Sys ems and [13] o a comple e lis
o e e ences o he bibliog aphy o P Sys ems.
In his pape we p esen ano he ex ension o P Sys ems, called P Sys ems wi h
Endosomes (PE Sys ems), wi h hese ea u es:
•objec s can be con ained bo h inside and on he su aces o he memb anes (as
in P Sys ems wi h pe iphe al p o eins [5, 9]);
• ules a e con ained on he su aces o he memb anes ( hey can ew i e objec s
ou side/on/in o he memb anes);
•endosomes can be explici ly c ea ed in o de o model a biologically inspi ed
anspo a ion mechanism.
The de ini ion o his ex ension o P Sys ems has a biological inspi a ion. In
ac , he endocy osis o mac omolecules is he p ocess by which cells abso b ma e-
ial (molecules such as p o eins) om ou side he cell by engul ing i wi h hei cell
memb ane. I is used by all cells o he body because mos subs ances impo an o
hem a e la ge pola molecules ha canno pass h ough he hyd ophobic plasma
memb ane o cell memb ane. The e exis h ee kind o endocy osis: phagocy osis,
pinocy osis and ecep o –media ed endocy osis. In pa icula , phagocy osis (li e -
ally, cell–ea ing) is he p ocess by which cells inges la ge objec s, such as cells
which ha e unde gone apop osis, bac e ia, o i uses. The memb ane olds a ound
he objec , and he objec is sealed o in o a la ge acuole known as a phago-
some. Pinocy osis (li e ally, cell–d inking) is conce ned wi h he up ake o solu es
and single molecules such as p o eins, and, inally, ecep o –media ed endocy osis
is a mo e speci ic ac i e e en whe e he cy oplasm memb ane olds inwa d o
o m coa ed pi s. These inwa d budding esicles bud o o m cy oplasmic esi-
cles. Figu e 11summa izes he kinds o endocy osis. By he poin o iew o he
modele , hese h ee p ocesses a e made possible by esicles (in ac his ans-
po a ion mechanism is known as esicle–media ed anspo a ion) which, in he
mos gene al case, engul he mac omolecules oge he wi h molecules om he
su ace o he memb anes (i.e. ecep o s). This leads o he c ea ion o endosomes
con aining he engul ed molecules. The endosomes ans e hei con en inside
he cell by possibly in e ac ing wi h o he componen s. The endosomes could also
be deg aded by he in e ac ion wi h he lysosomes. We de ine an ex ension o P
Sys ems (PE Sys ems) which can explici ly model he c ea ion o endosomes and
hei in e ac ion inside he cells and, consequen ly, can easily model hese h ee
kind o endocy osis.
This a ian o P Sys ems, oge he wi h o he modeling ea u es such as he
modeling o exocy osis ( he biologically coun e pa o endocy osis), and en iched
wi h channel–media ed communica ion [1], would p o ide a powe ul and comple e
modeling language o na u ally desc ibing anspo a ion mechanism o molecules
inside cells.
1Pic u es aken om h p://cellbiology.med.unsw.edu.au/uni s/science/lec u e0806.h m
P Sys ems wi h Endosomes 53
Fig. 1. Th ee kind o endocy osis: phagocy osis,pinocy osis and ecep o –media ed en-
docy osis.
We show ha PE Sys ems a e uni e sal e en i only he simples o m o
e olu ion ules is conside ed, namely non–coope a i e ules. Finally, we gi e one
applica ion examples o show ha endosomes can ease he desc ip ion o biological
sys ems when PE Sys ems a e used as a modeling o malism.
2 P Sys ems wi h Endosomes
In his sec ion we ecall he de ini ion o s anda d P Sys ems, and hen we de ine
hei ex ension wi h endosomes. We will deno e mul ise s o e a ini e alphabe as
s ings o alphabe symbols. Mo e p ecisely, le V∗be he se o all s ings o e
an alphabe V, including he emp y one, deno ed by λ. Fo a∈Vand xin V∗
we deno e by |x|a he numbe o occu ences o ain x. I V={a1,...,an}( he
o de ing is impo an he e), hen he Pa ikh mapping o xis de ined by ΨV(x) =
(|x|a1,...,|x|an). The de ini ion is ex ended in he na u al way o languages. A
s ing x ep esen s he mul ise o e Vwi h he mul iplici ies o objec s a1,...,an
as gi en by ΨV(x).
2.1 P Sys ems
A P Sys em consis s o a hie a chy o memb anes ha do no in e sec , wi h a
dis inguishable memb ane, called he skin memb ane, su ounding hem all. As
usual, we assume memb anes o be labeled by na u al numbe s. Gi en a se o
objec s V, a memb ane mcon ains a mul ise o objec s in V∗, a se o e olu ion
ules, and possibly o he memb anes, called child memb anes (mis also called
he pa en o i s child memb anes). Objec s ep esen molecules swimming in a
54 R. Ba bu i e al.
chemical solu ion, and e olu ion ules ep esen chemical eac ions ha may occu
inside he memb ane con aining hem. Fo each e olu ion ule he e is a mul ise
o objec s ep esen ing he eac an s, and a mul ise o objec s ep esen ing he
p oduc s o he chemical eac ion. A ule in a memb ane mcan be applied only
o objec s in m, meaning ha he eac an s should be p ecisely in m, and no
in i s child memb anes. The ule mus con ain a ge indica ions, speci ying he
memb anes whe e he new objec s p oduced by applying he ule a e sen . The
new objec s ei he emain in m, o can be sen ou o m, o can be sen in o one
o i s child memb anes, p ecisely iden i ied by i s label. Fo mally, he p oduc s o
a ule a e deno ed wi h a mul ise o messages o he o ms:
•( , he e), meaning ha he mul ise o objec s p oduced by he ule emain
in he same memb ane m;
•( , ou ), meaning ha he mul ise o objec s p oduced by he ule a e sen
ou o m;
•( , inl), meaning ha he mul ise o objec s p oduced by he ule a e sen
in o he child memb ane l.
Le TAR be he se o message a ge s {he e, ou } ∪ {ini|i∈N}. Gi en a se
o objec s Owe deno e wi h O a he co esponding se o messages O×TAR. As
a consequence, we deno e wi h V a he se o all messages and we can de ine an
e olu ion ule as a ule u→ such ha u∈V∗and ∈V∗
a .
The size o he le –hand side uo an e olu ion ule is also called he adius
o such a ule. I a P Sys em con ains ules o adius g ea e han one, hen i is
called a coope a i e sys em. O he wise, i is called non–coope a i e.
Applica ion o e olu ion ules is done wi h maximal pa allelism, namely a
each e olu ion s ep a mul ise o ins ances o e olu ion ules is chosen non–
de e minis ically such ha no o he ule can be applied o he sys em ob ained by
emo ing all he objec s necessa y o apply all he chosen ules.
A P Sys em has a ee–s uc u e in which he skin memb ane is he oo and he
memb anes con aining no o he memb anes a e he lea es. We assume memb anes
labels o be unique. A memb ane s uc u e can be ep esen ed as a balanced
sequence o labeled b acke s and, g aphically, as a Venn diag am.
De ini ion 1. AP Sys em is a uple (V, µ, w1,...,wn, R1,...,Rn)whe e:
•Vis a ini e alphabe whose elemen s a e called objec s;
•µ⊂N×Nis a memb ane s uc u e, such ha (i, j)∈µdeno es ha he
memb ane labeled by jis con ained in he memb ane labeled by i;
•wiwi h 1≤i≤na e s ings om V∗ ep esen ing mul ise s o e Vassocia ed
wi h he memb anes 1,2,...,n o µ;
•Riwi h 1≤i≤na e ini e se s o e olu ion ules associa ed wi h he mem-
b anes 1,2,...,n o µ;
A sequence o ansi ions be ween con igu a ions o a gi en P Sys em Πis called
acompu a ion. A compu a ion is success ul i and only i i eaches a con igu a ion
in which no ule is applicable. The esul o a success ul compu a ion is he mul ise
P Sys ems wi h Endosomes 55
1
EDa →(ED, he e)(aa, in2)
aD →(#, he e)
F Da →(F D, he e)(a, ou )
2
E→(G, he e)(ED, in2)
#→(#, he e)
a
EDa →(ED, he e)(a, ou )
aD →(#, ou )
E→(G, he e)(F D, ou )
E→(G, he e)(ED, ou )
GD →λ
ED
GD →λ
Fig. 2. Example o P Sys em ha compu es {a2n|n∈N}.
o objec s sen ou o he skin memb ane du ing he compu a ion. Unsuccess ul
compu a ions (compu a ions which ne e hal ) yield no esul . Gi en a P Sys em
Πwhose se o objec is V, he esul x∈V∗o a compu a ion o Πcan be
ep esen ed as he ec o o na u al numbe s ΦV(x). The se o all ec o s o
na u al numbe s compu ed by Πis deno ed P s(Π).
In Fig. 2 we show an example o P Sys em Π1compu ing {a2n|n∈N},
namely such ha Ps(Π1) = {2n|n∈N}. Ini ially, only in memb ane 2 he e
a e ules which a e applicable and send ei he objec s Fand Do objec s Eand
Din o memb ane 1. In he o me case he objec ain memb ane 1 is sen ou
and he compu a ion hal s. In he la e case objec ain memb ane 1 is consumed
and wo occu ences o aa e sen in o memb ane 2. Subsequen ly, Eis consumed
and sen in o memb ane 2 oge he wi h D. No e ha he ule which sends ED
in o memb ane 2 canno be applied while he e a e s ill objec s ain memb ane 1,
o he wise by he maximal pa allelism also he ule p oducing # would be applied
gi ing ise o an in ini e (unsuccess ul) compu a ion. Objec s asen in o memb ane
2 a e hen sen back in o memb ane 1. The p ocess o doubling and sending in o
memb ane 2 we ha e explained, could be epea ed an a bi a y numbe o imes.
No e ha all he ules consuming aac on a single occu ence o aa a ime and
hence he ime complexi y o he compu a ion is p opo ional o 2n+2.
2.2 Ex ension wi h Endosomes
In his sec ion we o mally de ine P Sys ems wi h endosomes (PE Sys ems). To his
ex en , we s a by assuming he same memb ane s uc u e µo a P Sys em. As
ega ds objec s, simila ly o P Sys ems wi h pe iphe al p o eins [5, 9], we assume
ha objec s can be con ained inside a memb ane (as in classical P Sys ems) and
on he su ace o a memb ane. In o de o quali y a posi ion o an objec wi h
espec o a memb ane, we use in o iden i y he objec inside he memb ane, ou
o iden i y he objec ou side he memb ane and he e o iden i y he objec on he
su ace o he memb ane. Le T AR be he se o message a ge s {in, ou , he e};
gi en a se o objec s Owe deno e wi h O a he co esponding se o messages
O×TAR, and we deno e wi h V a he se o all messages.

56 R. Ba bu i e al.
We can now in oduce he e olu ion ules o PE Sys ems; ules a e concep ually
di ided in e olu iona y ules (in he same sense o P Sys ems) and ules o he
c ea ion o endosomes. We ecall ha , di e en ly om P Sys ems, he ules o
PE Sys ems a e concep ually associa ed wi h he su aces o he memb anes o
he sys em. The o me class o ules a e o he o m u→ whe e u∈V+
a and
∈V∗
a . The de ini ion o coope a i e and non–coope a i e ules a e he same as
o P Sys ems.
No ice ha his o ma o e olu iona y ules, which a e syn ac ically di e en
om hose o P Sys ems, may seem o be less exp essi e han he one o P Sys-
ems, in pa icula o ule mo ing objec s in o speci ic memb anes (communica-
ion ules). In o de o show ha his is no he case, le us assume an hypo he ical
memb ane s uc u e µsuch ha (l, l′)∈µ, namely a memb ane s uc u e in which
l′is nes ed in o l. In o de o gi e a ule which mo es an objec inside memb ane
l′we canno use he iden i ie inl′in a ule o he su ace o he memb ane l(as in
P Sys ems) because we canno use he iden i ie l′as subsc ip o in. Howe e , he
same beha io can be ob ained by eplacing he ule u→( , inl′) in he memb ane
l, as in usual P Sys esm, wi h he PE Sys em ule (u, ou )→( , in) on he su ace
o he memb ane l′. The beha io modeled by his ule, which is in some sense
an “a ac ion” by he nes ed memb ane a he han he “sending” om he op
memb ane, leads o esul analogous o hose ob ained by P Sys ems, namely o
he anspo a ion o he objec inside he nes ed memb anes.
The ules o c ea ing endosomes a e o he o m endoE(u∈V∗, ∈V∗) whe e:
•Eis a se o e olu iona y ules o he endosome;
•uis he mul ise o objec s ha mus appea on he su ace o he memb ane
con aining he ule;
• is he mul ise o objec s ha mus appea ou side he memb ane con aining
he ule.
No ice ha each endosome has go i s own e olu iona y ules in se E. These ules
model he beha io o he endosome. As ega ds he c ea ion o an endosome, i is
necessa y ha objec s in ua e p esen on he su ace o he memb anes (in some
sense hey can be seen as he ecep o s) and ha objec s in a e p esen ou side
o he memb ane c ea ing he endosome (in some sense hey can be seen as he
molecules o be engul ed). Mo e o mally, he applicabili y o he endosome ule is
possible in he ollowing gene al case: le (j, i)∈µand le endoE(u, ) be a ule
belonging o he su ace o he memb ane i, han i can be applied only i uis a
submul ise o he objec s con ained on he su ace o he memb ane i, and only
i is a submul ise o he objec s con ained inside he memb ane j. The esul
o he applica ion o such a ule is a c ea ion o an endosome inside memb ane i
con aining uon i s su ace and con aining inside. The endosome i sel beha es
like a memb ane ha ing on i s su ace ules E.
We can now o mally de ine a PE Sys em as ollows.
De ini ion 2. APE Sys em is a uple (V, µ, w1,...,wn, z1,...,zn, R1,...,Rn)
whe e:
P Sys ems wi h Endosomes 57
•Vis an alphabe whose elemen s a e called objec s;
•µ⊂N×Nis a memb ane s uc u e, such ha (i, j)∈µdeno es ha he
memb ane labeled by jis con ained in he memb ane labeled by i;
•wiwi h 1≤i≤na e s ings om V∗ ep esen ing mul ise s o e Vassocia ed
wi h he con en o memb anes 1,2,...,n o µ;
•ziwi h 1≤i≤na e s ings om V∗ ep esen ing mul ise s o e Vassocia ed
wi h he su aces o memb anes 1,2,...,n o µ;
•Riwi h 1≤i≤na e ini e se s o e olu ion ules associa ed wi h he su aces
o he memb anes 1,2, . . . , n o µ.
The no ions o (success ul) compu a ion and o esul o compu a ions o PE
Sys ems a e he same as o s anda d P Sys ems.
3 Uni e sali y o PE Sys ems
In his sec ion we p o e a uni e sali y esul o PE Sys ems by showing ha any
ma ix g amma wi h appea ance checking can be simula ed by a PE Sys em.
As a consequence, be o e gi ing he esul and i s p oo , we ecall om [11] he
de ini ion o such a ian o ma ix g amma s and some ela ed no ions.
3.1 Ma ix g amma s wi h appea ance checking
A (con ex - ee) ma ix g amma wi h appea ance checking is a uple G=
(N, T, S, M, F ), whe e Nand Ta e disjoin alphabe s o non– e minals and e -
minals, espec i ely, S∈Nis he axiom, Mis a ini e se o ma ices, namely
sequences o he o m (A1→x1,...,An→xn) o con ex – ee ules o e N∪T
wi h n≥1, and Fis a se o occu ences o ules in he ma ices o M. Fo a s ing
w, a ma ix m: ( 1,... n) can be execu ed by applying i s ules o wsequen ially
in he o de in which he appea in m. Rules o a ma ix occu ing in Fcan be
skipped du ing he execu ion o he ma ix i hey canno be applied, namely i
he symbol in hei le –hand side is no p esen in he s ing.
Fo mally, gi en w, z ∈(N∪T)∗, we w i e w=⇒zi he e is a ma ix (A1→
x1,...,An→xn) in Mand he s ings wi∈(N∪T)∗wi h 1 ≤i≤n+ 1 such
ha w=w1,z=wn+1 and, o all 1 ≤i≤n, ei he (1) wi=w′
iAiw′′
iand
wi+1 =w′
ixiw′′
i, o some w′
i, w′′
i∈(N∪T)∗, o (2) wi=wi+1,Aidoes no appea
in wiand he ule Ai→xiappea s in F. We ema k ha Fconsis s o occu ences
o ules in M, ha is, i he same ule appea s se e al imes in he ma ices, i is
possible ha only some o hese occu ences a e con ained in F.
The language gene a ed by a ma ix g amma wi h appea ance checking Gis
de ined as L(G) = {w∈T∗|S=⇒∗w}, whe e =⇒∗wis he e lexi e and an-
si i e closu e o =⇒. The amily o languages o his o m is deno ed by MAT λ
ac,
when ules ha ing he emp y s ing λas igh hand side (λ– ules) a e allowed, and
58 R. Ba bu i e al.
by MATac when such ules a e no allowed. Mo eo e , he amily o languages gen-
e a ed by ma ix g amma s wi hou appea ance checking (i.e. wi h F=∅) is de-
no ed by MAT λ, when λ– ules a e allowed, and by MAT , when such ules a e no
allowed. I is known ha (i) MAT ⊂MATac ⊂CS; (ii) MAT λ⊂MATλ
ac =RE,
whe e CS and RE a e he amilies o languages gene a ed by con ex –sensi i e
and a bi a y g amma s, espec i ely.
Le ac(G) be he ca dinali y o Fin Gand le |x|deno e he leng h o he
s ing x. A ma ix g amma wi h appea ance checking G= (N, T, S, M, F ) is said
o be in he s ong bina y no mal o m i N=N1∪N2∪ {S, #}, wi h hese se s
mu ually disjoin , and he ma ices in Ma e in one o he ollowing o ms:
1. (S→XA), wi h X∈N1, A ∈N2;
2. (X→Y, A →x), wi h X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x| ≤ 2;
3. (X→Y, A →#), wi h X, Y ∈N1, A ∈N2;
4. (X→λ, A →x), wi h X∈N1, A ∈N2, x ∈T∗,|x| ≤ 2.
Mo eo e , he e is only one ma ix o ype 1, Fconsis s exac ly o all ules A→#
appea ing in ma ices o ype 3 and ac(G)≤2. We ema k ha # is a ap symbol,
namely once in oduced i canno be emo ed, and a ma ix o ype 4 is used only
once, in he las s ep o a de i a ion.
Fo each ma ix g amma (wi h o wi hou appea ance checking) he e exis s
an equi alen ma ix g amma in he s ong bina y no mal o m. Consequen ly, o
each language L∈RE he e exis s a ma ix g amma wi h appea ance checking
Gsa is ying he s ong bina y no mal o m and such ha L(G) = L.
Con en ions
A ma ix g amma wi h appea ance checking in he s ong bina y no mal o m
is always gi en as G= (N, T, S, M, F ), wi h N=N1∪N2∪ {S, #}and wi h
n+ 1 ma ices in M, injec i ely labeled wi h m0, m1,...,mn. The ma ix m0:
(S→Xini Aini ) is he ini ial one, wi h Xini a gi en symbol om N1and Aini
a gi en symbol om N2; he nex kma ices a e wi hou appea ance checking
ules, mi: (X→α, A →x), wi h 1 ≤i≤k, whe e X∈N1, α ∈N1∪ {λ}, A ∈
N2, x ∈(N2∪T)∗,|x| ≤ 2 (i α=λ, hen x∈T∗); he las n−kma ices ha e
ules o be applied in he appea ance checking mode, mi: (X→Y, A →#), wi h
k+ 1 ≤i≤n, X, Y ∈N1, and A∈N2.
Since he g amma is in he s ong bina y no mal o m, we ha e (a mos )
wo symbols B(1) and B(2) in N2such ha he ules B(j)→# appea in
ma ices miwi h k+ 1 ≤i≤n. Fo j∈ {1,2}, we deno e wi h ℓj he se
{i| he ma ix micon ains he ule B(j)→#}. Fo uni o mi y, we also deno e
ℓ0={1,2,...,k}and ℓ=ℓ0∪ℓ1∪ℓ2={1,2,...,n}(no e ha 0 6∈ ℓ). Clea ly,
he se s ℓ0, ℓ1and ℓ2a e disjoin .
We ema k ha in ma ix g amma s in s ong bina y no mal o ms we can
assume ha all symbols X∈N1appea as he le -hand side o a ule om
a ma ix: o he wise, he de i a ion is blocked a e in oducing such a symbol,
hence we can emo e hese symbols and he ma ices in ol ing hem.
P Sys ems wi h Endosomes 59
3.2 Uni e sali y
We p o e ha PMC Sys ems a e uni e sal by showing ha he amily, deno ed
PsE2(ncoo), o se s Ps(Πe) o esul s compu ed by PE Sys ems wi h a leas wo
memb anes and wi h non–coope a i e ules is equi alen o he amily, deno ed
PsRE, o he images o all he languages in RE ob ained h ough he Pa ikh
mapping ( his is he amily o ecu si ely enume able se s o ec o s o na u al
numbe s). As P Sys ems wi h non-coope a i e ules a e no uni e sal, ou esul
implies ha uni e sali y is due o he p esence o endosomes.
Theo em 1. PsE2(ncoo) = PsRE.
P oo . I is enough o show ha o a Gin s ong bina y no mal o m he e is a
PE Sys em ΠGsuch ha Ps(ΠG) = ΨT(L(G)). We assume ha he ou pu o his
PE Sys em is gi en by he objec s sen ou om he skin memb ane. The alphabe
we ake in o conside a ion is gi en by T∪N1∪N2∪ {c} ∪ {ci, di, d′
i|i= 1,2}. We
build ΠGas a sys em wi h a oo memb ane, labeled 1, and one child memb ane
labeled 2. All he objec s encoding he g amma will be s o ed inside memb ane
1 and he ma ixes will be simula ed by memb ane 2. The ini ial con igu a ion is
gi en by he objec s co esponding o Xini and Aini con ained in memb ane 1,
namely objec s o w1, and by he oken ccon ained on he su ace o memb ane
2, namely z2={c}.
This PE Sys em wo ks as ollows: i has a cyclic beha io such ha , a he
beginning o he cycle, a mos one endosome in memb ane 2 can be c ea ed and, i
possible, all e minal symbols inside memb ane 1 a e sen ou as ou pu symbols.
The c ea ed endosome can s a a se ies o s eps esul ing in he in e p e a ion
o he applica ion o a ma ix o , di e en ly, i can s a a checking phase o
model he ac ha , i he e exis non e minal symbols which canno be ew i en
by any g amma , han he compu a ion has no o hal . In he case in which
i s a s he in e p e a ion o a ma ix o ype 2 o 4 (a ma ix miwi h 1 ≤
i≤k), he in ol ed non e minals a e aken by he endosome which con ains as
ules he ones in e p e ing he ma ix. Objec s will be sen in o memb ane 2 by
hese ules c ea ing he esul o applying he co esponding ma ix o he non
e minals. Subsequen ly, hese objec s a e sen ou o memb ane 1 o es a he
cyclic beha io . We ecall ha du ing his p ocess no o he endosomes can be
c ea ed, so no o he ma ixes can be simula ed. Di e en ly, in he case in which a
ma ix o ype 3 (a ma ix miwi h k+1 ≤i≤n) is applied, he single non e minal
o N1is aken in o he endosome. The endosome will wo k in he same sense o
he endosomes in e p e ing ma ixes o ype 2 and 4 e en hough, a he end
o he applica ion o his ma ix, ins ead o es a ing wi h he cyclic beha io ,
a checking p ocess is s a ed. This p ocess checks, by c ea ing endosomes, he
p esence o he p ope non e minal symbol B(j). I his symbol is ound, a special
endosome is c ea ed which will in oduce a ap symbol in his PE Sys em so ha
he compu a ion will no hal . Analogously, i i is no ound, an endosome will
es o e he con igu a ion o his PE Sys em so ha he cyclic beha io can s a
again.