Decidabili y o Di e gence o Ca aly ic P
Sys ems
Nadia Busi
Dipa imen o di Scienze dell’In o mazione
Uni e si `a di Bologna
Mu a A. Zamboni 7, I-40127 Bologna, I aly
[email p o ec ed]
Summa y. P sys ems a e a biologically inspi ed model in oduced by Gheo ghe P˘aun
wi h he aim o ep esen ing he s uc u e and he unc ioning o he cell. Since hei
in oduc ion, se e al a ian s o P sys ems ha e been p oposed and explo ed.
We concen a e on he class o ca aly ic P sys ems wi hou p io i ies associa ed o
he ules. We show ha he di e gence p oblem (i.e., checking o he exis ence o an
in ini e compu a ion) is decidable in such a class o P sys ems.
As a co olla y, we ob ain an al e na i e p oo o he nonuni e sali y o de e minis ic
ca aly ic P sys ems, an open p oblem ecen ly sol ed by Iba a and Yen.
1 In oduc ion
Memb ane compu ing is a b anch o na u al compu ing, ini ia ed by Gheo ghe
P˘aun wi h he de ini ion o P sys ems in [11, 12, 13]. The aim is o p o ide a o mal
modeling o he s uc u e and he unc ioning o he cell, making use especially o
au oma a, languages and complexi y heo e ic ools.
Quo ing om he Milano webpage [17], “A P sys em is a compu ing model
which abs ac s om he way he ali e cells p ocess chemical compounds in hei
compa men al s uc u e. In sho , in he egions de ined by a memb ane s uc-
u e we ha e objec s which e ol e acco ding o gi en ules. The objec s can be
desc ibed by symbols o by s ings o symbols (in he o me case hei mul iplic-
i y ma e s, ha is, we wo k wi h mul ise s o objec s placed in he egions o he
memb ane s uc u e; in he second case we can wo k wi h languages o s ings o ,
again, wi h mul ise s o s ings). By using he ules in a nonde e minis ic, max-
imally pa allel manne , one ge s ansi ions be ween he sys em con igu a ions.
A sequence o ansi ions is a compu a ion. Wi h a hal ing compu a ion we can
associa e a esul , in he o m o he objec s p esen in a gi en memb ane in he
hal ing con igu a ion, o expelled om he sys em du ing he compu a ion. Va -
ious ways o con olling he ans e o objec s om a egion o ano he one and
64 N. Busi
o applying he ules, as well as possibili ies o dissol e, di ide, c ea e, o mo e
memb anes we e conside ed.”
Since hei in oduc ion, plen y o a ian s o P sys ems ha e been in oduced,
and a lo o esea ch e o has been ca ied ou , especially conce ned wi h he
s udy o he exp essi i y and he uni e sali y o he p oposed models and wi h he
abili y o sol e NP-comple e p oblems in polynomial ime.
In his pape we concen a e on ca aly ic P sys ems, namely sys ems whose
ules a e o one o he ollowing kinds:
•con ex – ee ules, wi h he o m a→ and ep esen ing he ac ha an
ins ance o ais consumed and he objec s in a e p oduced, o
•ca aly ic ules, wi h he o m ca →c and ep esen ing he ac ha ais
consumed and he objec s in a e p oduced, p o ided ha an ins ance o
ca alys cis p esen inside he memb ane, and ha such an ins ance o chas
no been used ye by ano he concu en ly execu ed ule. As we will see in
Sec ion 3, ca alys s a e nei he p oduced no consumed by e olu ion ules, bu
hey a e used o bound he numbe o ins ances o ca aly ic ules applied in a
maximal pa allelism s ep.
The compu a ional powe o ca aly ic P sys ems has been ackled in a ious
pape s: in [12] he uni e sali y o P sys ems wi h ca alys s and p io i ies is p o ed;
he esul has been imp o ed in [15, 16] by showing ha p io i ies a e no necessa y
o uni e sali y. In [5, 4] some minimali y p ope ies o uni e sali y a e in es i-
ga ed; in pa icula , [4] shows ha wo ca alys s a e su icien o ge uni e sali y.
Howe e , he encodings p esen ed in he a o emen ioned wo ks p esen a high
deg ee o nonde e minism. Fo example, in [4] an encoding o de e minis ic Min-
sky’s egis e machines [10] is p o ided, ha sa is ies he ollowing p ope ies:
•i he egis e machine hal s, hen he encoding o he egis e machine has a
hal ing compu a ion (bu he e could also be o he non e mina ing compu a-
ions);
•i he egis e machine does no hal , hen all he compu a ions o he encoding
a e non e mina ing.
A co olla y o his esul is he undecidabili y o he exis ence o an hal ing com-
pu a ion o ca aly ic P sys ems, bu he nonde e minis ic na u e o he encoding
lea es he doo open o he possibili y o o he p ope ies o be decidable. This
ac is qui e ele an om he poin o iew o sys ems biology, whe e he in e es
is o p edic he beha io o he li ing ma e .
In he p esen pape we show ha di e gence, namely, he exis ence o a non e -
mina ing compu a ion, is decidable o ca aly ic P sys ems. The p oo is based on
he heo y o well-s uc u ed ansi ion sys ems [3]: he exis ence o an in ini e com-
pu a ion s a ing om a gi en s a e is decidable o ini ely b anching ansi ion
sys ems, p o ided ha he se o s a es can be equipped wi h a well-quasi-o de ing,
i.e., a quasi-o de ing ela ion which is compa ible wi h he ansi ion ela ion and
such ha each in ini e sequence o s a es admi s an inc easing subsequence. To
his aim, we de ine a quasi-o de ing on he con igu a ions o ca aly ic P sys ems
Decidabili y o Di e gence o Ca aly ic P Sys ems 65
ha u ns ou o be a well-quasi-o de ing compa ible wi h he maximally pa allel
e olu ion ule.
A consequence o his esul is he impossibili y o p o ide a de e minis ic en-
coding o any Tu ing powe ul o malism in ca aly ic P sys ems, as o de e minis-
ic sys ems di e gence and he exis ence o an hal ing compu a ion a e equi alen
p ope ies. This yields o an al e na i e p oo o he nonuni e sali y o de e min-
is ic ca aly ic P sys ems, an open p oblem aised in [6, 14] and ecen ly sol ed by
Iba a and Yen [8, 9].
The pape is o ganized as ollows. A e p o iding some basic de ini ions in
Sec ion 2, in Sec ion 3 we de ine ca aly ic P sys ems. Sec ion 4 is de o ed o
ecalling some basic no ions and esul s conce ning well-quasi-o de ings and well-
s uc u ed ansi ion sys ems ha will be used in he ollowing. Sec ion 5 is de o ed
o he decidabili y esul : a e p o iding a ine no ion o he con igu a ions and
e olu ion ules o ca aly ic P sys ems ha is sui able o ou aims, we de ine a
quasi-o de ing ela ion on he con igu a ions and show ha i u ns ou o be
a well-quasi-o de ing compa ible wi h he maximally pa allel e olu ion ule, and
inally we make use o he heo y o well-s uc u ed ansi ion sys ems o ge he
decidabili y o di e gence. Some conclusi e ema k is epo ed in Sec ion 6.
2 Basic de ini ions
In his sec ion we p o ide some de ini ions ha will be used h oughou he pape .
We s a wi h he de ini ion o mul ise s and mul ise ope a ions.
De ini ion 1. Gi en a se S, a ini e mul ise o e Sis a unc ion m:S→IN
such ha he se dom(m) = {s∈S|m(s)6= 0}is ini e. The mul iplici y o
an elemen sin mis gi en by he na u al numbe m(s). The se o all ini e
mul ise s o e S, deno ed by M in(S), is anged o e by m. A mul ise msuch
ha dom(m) = ∅is called emp y. The emp y mul ise is deno ed by ∅.
Gi en he mul ise mand m0, we w i e m⊆m0i m(s)≤m0(s) o all s∈S
while ⊕deno es hei mul ise union:m⊕m0(s) = m(s) + m0(s). The ope a o
deno es mul ise di e ence:(m m0)(s) = i m(s)≥m0(s) hen m(s)−m0(s)else
0. The scala p oduc ,j·m, o a numbe jwi h mis (j·m)(s) = j·(m(s)). The
ca dinali y o a mul ise is he numbe o occu ences o elemen s con ained in he
mul ise : |m|=Ps∈Sm(s).
The se o pa s o a se Sis de ined as P(S) = {X|X⊆S}.
The es ic ion o a subse o a mul ise is de ined as ollows:
De ini ion 2. Le mbe a ini e mul ise o e Sand X⊆S. The mul ise m|Xis
de ined as ollows: o all s∈S,
m|X(s) = ½m(s)i s∈X,
0o he wise.
We p o ide some basic de ini ions on s ings, ca esian p oduc s and ela ions.
66 N. Busi
De ini ion 3. A s ing o e Sis a ini e (possibly emp y) sequence o elemen s in
S. Gi en a s ing u=x1. . . xn, he leng h o uis he numbe o occu ences o
elemen s con ained in uand is de ined as ollows: |u|=n.
Wi h S∗we deno e he se o s ings o e S, and u, , w, . . . ange o e S.
Gi en n≥0, wi h Snwe deno e he se o s ings o leng h no e S.
Gi en a s ing u=x1. . . xnand isuch ha 1≥i≥n, wi h (u)iwe deno e he
i- h elemen o u, namely, (u)i=xi.
Gi en a s ing u=x1. . . xn, he mul ise co esponding o uis de ined as
ollows: o all s∈S,mu(s) = |{i|xi=s∧1≤i≤n}|. Wi h abuse o no a ion,
we use u o deno e also mu.
De ini ion 4. Wi h S×Twe deno e he ca esian p oduc o se s Sand T, wi h
×nS,n≥1, we deno e he ca esian p oduc o ncopies o se Sand wi h ×n
i=1Si
we deno e he ca esian p oduc o se s S1, . . . , Sn, i.e., S1×. . . ×Sn. The i h
p ojec ion o (x1, . . . , xn)∈ ×n
i=1Siis de ined as πi(x) = xi, and li ed o subse s
X⊆ ×n
i=1Sias ollows: πi(X) = {πi(x)|x∈X}.
Gi en a bina y ela ion Ro e a se S, wi h Rnwe deno e he composi ion o
nins ances o R, wi h R+we deno e he ansi i e closu e o R, and wi h R∗we
deno e he e lexi e and ansi i e closu e o R.
3 Ca aly ic P Sys ems
We ecall he de ini ion o ca aly ic P sys ems wi hou p io i ies on ules p o ided
in [4]. Fo a ho ough desc ip ion o he model, mo i a ion and examples see, e.g.,
[1, 2, 11, 12, 13].
To his aim, we s a wi h he de ini ion o a memb ane s uc u e:
De ini ion 5. Gi en he alphabe V={[,]}, he se MS is he leas se induc i ely
de ined by he ollowing ules:
•[ ] ∈MS,
•i µ1, µ2, . . . , µn∈MS,n≥1, hen [µ1. . . µn]∈MS.
We de ine he ollowing ela ion o e MS:x∼yi he wo s ings can be w i -
en in he o m x= [1...[2. . .]2...[3. . .]3. . .]1and y= [1. . . [3. . .]3...[2. . .]2...]1
(i.e., i wo pai s o pa en hesis ha a e neighbo s can be swapped oge he wi h
hei con en s).
The se MS o memb ane s uc u es is de ined as he se o equi alence classes
w. . . he ela ion ∼∗.
We call a memb ane each ma ching pai o pa en hesis appea ing in he mem-
b ane s uc u e. A memb ane s uc u e µcan be ep esen ed as a Venn diag am,
in which any closed space (delimi ed by a memb ane and by he memb anes im-
media ely inside) is called a egion o µ.
Decidabili y o Di e gence o Ca aly ic P Sys ems 67
De ini ion 6. Aca aly ic P sys em (o deg ee d, wi h d≥1) is a cons uc
Π= (V, C, µ, w0
1, . . . , w0
d, R1, . . . , Rd, i0),
whe e:
1. Vis a ini e alphabe whose elemen s a e called objec s;
2. C⊆Vis a se o ca alys s;
3. µis a memb ane s uc u e consis ing o dmemb anes (usually labeled wi h i
and ep esen ed by co esponding b acke s [iand ]i, wi h 1≤i≤d);
4. w0
i,1≤i≤d, a e s ings o e Vassocia ed wi h he egions 1,2, . . . , d o µ;
hey ep esen mul ise s o objec s p esen in he egions o µ( he mul iplici y
o a symbol in a egion is gi en by he numbe o occu ences o his symbol in
he s ing co esponding o ha egion);
5. Ri,1≤i≤d, a e ini e se s o e olu ion ules o e Vassocia ed wi h he
egions 1,2, . . . , d o µ; hese e olu ion ules a e o he o ms a→ o ca →
c , whe e cis a ca alys , ais an objec om V C, and is a s ing om
((V C)× {he e, ou , in})∗;
6. i0is a numbe be ween 1and dand i speci ies he ou pu memb ane o Π.
The memb ane s uc u e and he mul ise s ep esen ed by wi, 1 ≤i≤d, in Π
cons i u e he ini ial s a e1o he sys em. A ansi ion be ween s a es is go e ned
by an applica ion o he e olu ion ules which is done in pa allel; all objec s, om
all memb anes, which can be he subjec o local e olu ion ules ha e o e ol e
simul aneously.
The applica ion o a ule2u→ in a egion con aining a mul ise m esul s in
sub ac ing om m he mul ise iden i ied by u, and hen in adding he mul ise
de ined by . The objec s can e en ually be anspo ed h ough memb anes due
o he a ge s in and ou (we usually omi he a ge he e). No e ha he ca alys s
a e nei he c ea ed no des oyed by he applica ion o he ules: hey simply bound
he numbe o occu ences o (pa icula se s o ) ules in a maximal pa allelism
s ep. Mo eo e , ca alys s canno mo e ac oss he memb anes.
The sys em con inues pa allel s eps un il he e emain no applicable ules in
any egion o Π; hen he sys em hal s. We conside he numbe o objec s om
Vcon ained in he ou pu memb ane i0when he sys em hal s as he esul o he
unde lying compu a ion o Π.
We say ha a P sys em Πdi e ges i he e exis s an in ini e compu a ion
s a ing om he ini ial s a e o Π.
Fo example, a g aphical ep esen a ion o he ini ial s a e o he P sys em
Π1= ({a, b, c},{c},[1[2]2]1, aabc, abc, {a→b, cb →ca, ca →caa},{ca →cb, cb →
cba},1) is depic ed in Figu e 1.
1He e we use he e m s a e ins ead o he classical e m con igu a ion because we will
de ine a (essen ially equi alen bu syn ac ically) di e en no ion o con igu a ion in
Sec ion 5.
2We use u→ as a sho hand o deno e bo h he ules o kind a→wand ca →cw.

68 N. Busi '
&
$
%
'
&
$
%
1
2
aabc
a→b
cb →ca
ca →caa
abc
ca →cb
cb →cba
Fig. 1. The ini ial s a e o he P sys em Π1.
E en i bo h a copy o aand a copy o ba e p esen in he memb ane 1 in he
ini ial s a e, ules cb →ca and ca →caa canno be applied oge he in he same
s ep, as only a single ins ance o ca alys cis p esen in such a s a e.
We in oduce a couple o unc ions on memb ane s uc u es ha will be use ul
in he ollowing:
De ini ion 7. Le µbe a memb ane s uc u e consis ing o dmemb anes, labelled
wi h {1, . . . , d}.
Gi en wo memb anes iand jin µ, we say ha he iis con ained in ji he
su ace delimi ed by he pe ime e o iin he Venn diag am ep esen a ion o µis
con ained inside he pe ime e o j.
We say ha iis he a he o j(and jis a child o i) i he memb ane jis
con ained in i, and no memb ane exis s ha con ains jand is con ained in i.
The pa ial unc ion a he :{1, . . . , d}→{1, . . . , d} e u ns he a he o a
memb ane i, o is unde ined i iis he ex e nal memb ane.
The unc ion child en :{1, . . . , d}→P({1, . . . , d}) e u ns he se o child en
o a memb ane.
Fo example, ake µ= [1[2[3]3]2[4]4]1; hen, a he (2) = a he (4) = 1,
a he (3) = 4 and a he (1) is unde ined; mo eo e , child en(4) = ∅and
child en(1) = {2,4}.
4 Well-S uc u ed T ansi ion Sys ems
We s a by ecalling some basic de ini ions and esul s om [3], conce ning well-
s uc u ed ansi ion sys ems, ha will be used in he ollowing.
Aquasi-o de ing (qo) is a e lexi e and ansi i e ela ion.
De ini ion 8. Awell-quasi-o de ing (wqo) is a quasi-o de ing ≤o e a se Xsuch
ha , o any in ini e sequence x0, x1, x2, . . . in X, he e exis subsc ip s i < j such
ha xi≤xj.
Decidabili y o Di e gence o Ca aly ic P Sys ems 69
No e ha , i ≤is a wqo, hen any in ini e sequence x0, x1, x2, . . . con ains an
in ini e inc easing subsequence xi0, xi1, xi2, . . . (wi h i0< i1< i2< . . .).
T ansi ion sys ems can be o mally de ined as ollows.
De ini ion 9. A ansi ion sys em is a s uc u e T S = (S, →), whe e Sis a se
o s a es and →⊆ S×Sis a se o ansi ions.
We w i e Succ→(s) o deno e he se {s0∈S|s→s0}o immedia e successo s o
s∈S.
TS is ini ely b anching i ∀s∈S:Succ(s)is ini e. We es ic o ini ely b anch-
ing ansi ion sys ems.
Well-s uc u ed ansi ion sys ems, de ined as ollows, p o ide he key ool o
decide p ope ies o compu a ions.
De ini ion 10. Awell-s uc u ed ansi ion sys em (wi h s ong compa ibili y)
is a ansi ion sys em T S = (S, →), equipped wi h a quasi-o de ing ≤on S, also
w i en T S = (S, →,≤), such ha he ollowing wo condi ions hold:
1. well-quasi-o de ing:≤is a well-quasi-o de ing, and
2. s ong compa ibili y:≤is (upwa d) compa ible wi h →, i.e., o all s1≤ 1
and all ansi ions s1→s2, he e exis s a s a e 2such ha 1→ 2and
s2≤ 2.
The ollowing heo em (a special case o a esul in [3]) will be used o ob ain
ou decidabili y esul .
Theo em 1. Le T S = (S, →,≤)be a ini ely b anching, well-s uc u ed ansi-
ion sys em wi h decidable ≤and compu able Succ. The exis ence o an in ini e
compu a ion s a ing om a s a e s∈Sis decidable.
To show ha he quasi-o de ing ela ion we will de ine on P sys ems is a well-
quasi-o de ing we need he ollowing esul s on well-quasi-o de ing ela ions o
ini e se s and mul ise s.
P oposi ion 1. Le Sbe a ini e se . Then he equali y is a wqo o e S.
Lemma 1. [Dickson] Le Sbe a ini e se . The ela ion ⊆is a wqo o e M in(S).
The ollowing p oposi ion pe mi s o ob ain a well-quasi-o de ing on he ca e-
sian p oduc o se s equipped wi h well-quasi-o de ings:
P oposi ion 2. Le Sibe se s and ≤i, be wqo o e Si, o i= 1, . . . , n. The
ela ion ≤o e ×n
i=1Siis de ined as ollows: x≤yi πi(x)≤iπi(y) o i=
1, . . . , n. The ela ion ≤is a wqo o e ×n
i=1Si.
70 N. Busi
5 Decidabili y o Di e gence o Ca aly ic P Sys ems
In his sec ion we show ha he exis ence o a di e gen compu a ion is decidable
o he class o ca aly ic P sys ems de ined in Sec ion 3.
The decidabili y p oo is based on he heo y o well-s uc u ed ansi ion sys-
ems [3]: he exis ence o an in ini e compu a ion s a ing om a gi en s a e is
decidable o ini ely b anching ansi ion sys ems, p o ided ha he se o s a es
can be equipped wi h a well-quasi-o de ing, i.e., a quasi-o de ing ela ion which
is compa ible wi h he ansi ion ela ion and such ha each in ini e sequence o
s a es admi s an inc easing subsequence.
To his aim, we need a ine de ini ion o he compu a ion o a P sys em, whe e
a maximal pa allelism e olu ion s ep is ep esen ed as a (maximal) sequence o
simple e olu ion s eps, which a e ob ained by he applica ion o a single e olu ion
ule.
A e de ining such p elimina y no ions, we p opose a well-quasi-o de ing ha
u ns ou o be compa ible wi h he maximal pa allelism e olu ion s ep.
5.1 Pa ial con igu a ions, eac ion ela ion, and maximal pa allelism
s ep
To ep esen he s a es o he sys em eached a e he execu ion o a non-maximal
sequence o simple e olu ion ules, we in oduce he no ion o pa ial con igu a ion
o a sys em. In a pa ial con igu a ion, he con en s o each egion is ep esen ed
by wo mul ise s:
•The mul ise o ac i e objec s con ains he objec s ha we e in he egion a
he beginning o he cu en maximal pa allelism e olu ion s ep. These objec s
can be used by he nex simple e olu ion s ep.
•The mul ise o ozen objec s con ains he objec s ha ha e been p oduced in
he egion du ing he cu en maximal pa allelism e olu ion s ep. These objec s
will be a ailable o consump ion in he nex maximal pa allelism e olu ion
s ep.
De ini ion 11. Le Π= (V, C, µ, w0
1, . . . , w0
d, R1, . . . , Rd, i0)be a ca aly ic P sys-
em.
Apa ial con igu a ion o Πis a uple (w1,¯w1), . . . , (wd,¯wd)∈ ×d(V×V).
We use ×d
i=1(wi,¯wi) o deno e he pa ial con igu a ion abo e.
The se o pa ial con igu a ions o Πis deno ed by Con Π. We use γ, γ0, γ1, . . .
o ange o e Con Π.
In he abo e de ini ion, w1, . . . , wd ep esen he ac i e mul ise s, whe eas
¯w1, . . . , ¯wd ep esen he ozen mul ise s.
Fo example, ((aabc, ∅),(abc, ∅)) and ((abc, cb),(c, ∅)) a e pa ial con igu a ions
(no necessa ily eachable om he ini ial s a e) o he P sys em in Figu e 1.
Acon igu a ion is a pa ial con igu a ion con aining no ozen objec s; con ig-
u a ions ep esen he s a es eached a e he execu ion o a maximal pa allelism
compu a ion s ep.
Decidabili y o Di e gence o Ca aly ic P Sys ems 71
De ini ion 12. Le Π= (V, C, µ, w0
1, . . . , w0
d, R1, . . . , Rd, i0)be a ca aly ic P sys-
em.
Acon igu a ion o Πis a pa ial con igu a ion ×d
i=1(wi,¯wi)sa is ying he ol-
lowing: ¯wi=∅ o i= 1, . . . , d.
The ini ial con igu a ion o Πis he con igu a ion ×d
i=1(w0
i,∅).
Fo example, ((aabc, ∅),(abc, ∅)) is a con igu a ion (ac ually he ini ial con ig-
u a ion) o he P sys em in Figu e 1, whe eas he pa ial con igu a ion ((ab, caa),
(abc, ∅)) is no a con igu a ion.
The size o a pa ial con igu a ion is he numbe o ac i e objec s con ained in
he con igu a ion; i will be used o p o e he esul s in he ollowing pa o he
pape :
De ini ion 13. Le Π= (V, C, µ, w0
1, . . . , w0
d, R1, . . . , Rd, i0)be a ca aly ic P sys-
em and γ=×d
i=1(wi,¯wi)be a pa ial con igu a ion. The size o γis #(γ) =
Pd
i=1 |wi|.
The execu ion o a simple e olu ion ule is o malized by he no ion o eac ion
ela ion, de ined as ollows:
De ini ion 14. Le Π= (V, C, µ, w0
1, . . . , w0
d, R1, . . . , Rd, i0)be a ca aly ic P sys-
em.
The eac ion ela ion 7→ o e Con Π×Con Πis de ined as ollows:
×d
i=1(wi,¯wi)7→ ×d
i=1(w0
i,¯w0
i)i he e exis k, wi h 1≤k≤d, an e olu ion
ule u→ ∈Rkand a mig a ion s ing ρ∈ {1, . . . , d}| |such ha
•u⊆wk,
•w0
k=wk u,
• ∀i: 1 ≤i≤dand i6=kimplies w0
i=wi,
• ∀j: 1 ≤j≤ | | he ollowing holds:
– i π2(( )j) = he e, hen (ρ)j=k,
– i π2(( )j) = ou , hen3(ρ)j= a he (k),
– i π2(( )j) = in, hen4(ρ)j∈child en(k),
• ∀i, 1≤i≤d: ¯w0
k= ¯wk⊕L1≤j≤| |,(ρ)j=k( )j.
Fo example, in he P sys em o Figu e 1
((aabc, ∅),(abc, ∅)) 7→ ((ab, caa),(abc, ∅)),
((ab, caa),(abc, ∅)) 7→ ((ab, caa),(a, cba)),
((ab, caa),(a, cba)) 67→ ((ab, cab),(a, cba)).
No e ha he size o a con igu a ion ep esen s an uppe bound o he leng h
o he sequences o eac ions s a ing om ha con igu a ion. Hence, in ini e se-
quences o eac ions a e no possible.
3As ρ∈ {1, . . . , d}| |, his implies ha a he (k) is de ined.
4This implies ha child en(k) is no emp y.
78 N. Busi
6 Conclusion
In his pape we showed ha he exis ence o a di e gen compu a ion is a decid-
able p ope y o ca aly ic P sys ems.
As a byp oduc , we also ob ain an al e na i e p oo o he nonuni e sali y o
de e minis ic ca aly ic P sys ems, an open p oblem ecen ly sol ed by Iba a and
Yen [8, 9]. Ac ually, he decidabili y o di e gence pe mi s o de i e a sligh ly mo e
gene al esul , i.e., he nonuni e sali y o he class o P sys ems which is uni o m
w. . . e mina ion (we say ha a P sys em is uni o m w. . . e mina ion i he
ollowing p ope y holds: he P sys ems has a e mina ing compu a ion i all o
i s compu a ions e mina e).
Finally, as in [4], we conside P sys ems wi hou p io i ies associa ed o he
ules. A de ailed in es iga ion o he exp essi i y o a ious classes o de e minis ic
P sys ems wi h p io i ies has been ca ied ou in [8, 9]. An in es iga ion o he
impac o he in oduc ion o p io i ies on ou esul is le o u u e in es iga ion.
In he p esen pape we showed ha di e gence is a decidable p ope y o ca -
aly ic P sys ems. The echnique employed o p o e he decidabili y o di e gence is
based on he heo y o well-s uc u ed ansi ion sys ems: besides uni e sal e mi-
na ion, such a heo y pe mi s o analyse o he in e es ing p ope ies, such as, e.g.,
co e abili y, boundedness, and e en uali y p ope ies [3]. We plan o in es iga e
he possibili y o use his heo y o he analysis o o he (biologically ele an )
p ope ies.
Acknowledgemen : I’m g a e ul o Geo ge P˘aun, Osca Iba a and, las bu
no leas , Claudio Zand on o hei p ecious commen s and sugges ions.
Re e ences
1. C.S. Calude, G. P˘aun: Compu ing wi h Cells and A oms. Taylo & F ancis, London,
2001.
2. J. Dassow, G. P˘aun: On he powe o memb ane compu ing. J. Uni . Compu . Sci.,
5, 2 (1999).
3. A. Finkel, Ph. Schnoebelen: Well-s uc u ed ansi ion sys ems e e ywhe e! Theo e -
ical Compu e Science, 256 (2001), 63–92.
4. R. F eund, L. Ka i, M. Oswald, P. Sosik: Compu a ionally uni e sal P sys ems wi h-
ou p io i ies: wo ca alys s a e su icien . Theo e ical Compu e Science, 330 (2005).
5. R. F eund, M. Oswald, P. Sosik: Reducing he numbe o ca alys s needed in compu-
a ionally uni e sal sys ems wi hou p io i ies. In P oc. Fi h In e na ional Wo kshop
on Desc ip ional Complexi y o Fo mal Sys ems, Budapes , 2003.
6. R. F eund, Gh. P˘aun: On de e minis ic P sys ems. Manusc ip , 2003. (See he Milano
webpage [17]).
7. O.H. Iba a: Some ecen esul s conce ning de e minis ic P sys ems. In P oc 6 h
In e na ional Wo kshop on Memb ane Compu ing (WMC6), LNCS 3850, Sp inge ,
2006.

Decidabili y o Di e gence o Ca aly ic P Sys ems 79
8. O.H. Iba a, H.-C. Yen: On de e minis ic ca aly ic P sys ems. In P oc. 10 h In e -
na ional Con e ence on Implemen a ion and Applica ion o Au oma a (CIAA2205),
LNCS 3845, Sp inge , 2005.
9. O.H. Iba a, H.-C. Yen: De e minis ic ca aly ic sys ems a e no uni e sal. Submi ed,
2006.
10. M.L. Minsky: Compu a ion: Fini e and In ini e Machines. P en ice-Hall, Englewood
Cli s, 1967.
11. Gh. P˘aun: Compu ing wi h memb anes: an in oduc ion. Bull. EATCS, 67 (1999).
12. Gh. P˘aun: Compu ing wi h memb anes. Jou nal o Compu e and Sys em Sciences,
61, 1 (2000), 108–143.
13. Gh. P˘aun: Memb ane Compu ing. An In oduc ion. Sp inge , Be lin, 2002.
14. Gh. P˘aun: Fu he wen y–six open p oblems in memb ane compu ing. In P oc. Thi d
B ains o ming Week on Memb ane Compu ing, Se illa, 2005.
15. P. Sosik: The powe o ca alys s and p io i ies in memb ane sys ems. G amma s, 6,
1 (2003).
16. P. Sosik, R. F eund: P Sys ems wi hou p io i ies a e compu a ionally uni e sal.
In P oc. Memb ane Compu ing. In e na ional Wo kshop, WMC-CdeA 2002, LNCS
2597, Sp inge , 2003.
17. P Sys ems webpage: h p://psys ems.disco.unimib.i .