Pu ely Ca aly ic P Sys ems o e In ege s
and Thei Gene a i e Powe
A iom Alhazo 1, Oma Belinghe i2, Rudol F eund3,
Se giu I ano 4, An onio E. Po eca2, and Claudio Zand on2
1Ins i u e o Ma hema ics and Compu e Science
Academy o Sciences o Moldo a
S . Academiei 5, Chi¸sin˘au, MD 2028, Moldo a
E-mail: [email p o ec ed]
2Dipa imen o di In o ma ica, Sis emis ica e Comunicazione
Uni e si `a degli S udi di Milano-Bicocca
Viale Sa ca 336/14, 20126 Milano, I aly
E-mail: {o.belinghe i@campus,po eca@disco,zand on@disco}.unimib.i
3Facul y o In o ma ics, TU Wien
Fa o i ens aße 9-11, 1040 Vienna, Aus ia
E-mail: [email p o ec ed]
4Uni e si ´e Pa is Es , F ance
E-mail: [email p o ec ed]
Summa y. We u he in es iga e he compu ing powe o he ecen ly in oduced P
sys ems wi h Z-mul ise s (also known as hyb id se s) as gene a i e de ices. These sys ems
apply ca aly ic ules in he maximally pa allel way, e en consuming absen non-ca alys s,
e ec i ely gene a ing ec o s o a bi a y (no jus non-nega i e) in ege s. The ules may
be made inapplicable only by dissolu ion ules. Howe e , his eleases he ca alys s in o
he immedia ely ou e egion, whe e new ules migh become applicable o hem. We
discuss he gene a i e powe o his model. Finally, we conside he a ian wi h mobile
ca alys s.
1 In oduc ion
Memb ane sys ems (cell-like, wi h symbol-objec s) ha e adi ionally been iewed
as collec ions o hie a chically a anged mul ise p ocesso s [12]. In he lis o
open p oblems dissemina ed in 2015 [11], Gheo ghe P˘aun sugges ed going beyond
he adi ional se ing whe e symbol mul iplici ies in mul ise s a e es ic ed o
non-nega i e in ege s. One sugges ed app oach [6] de ines gene alized mul ise s as
aking mul iplici ies om a bi a y ini ely gene a ed, o ally o de ed commu a i e
g oups.
In wo k [3], a di e en app oach is aken: only ca aly ic ules a e allowed, and
he applicabili y o a ule only depends on p esence o he co esponding ca alys
16 A. Alhazo , O. Belinghe i, R. F eund, S. I ano , A.E. Po eca, C. Zand on
in he gi en egion. Consuming an absen non-ca alys makes i s mul iplici y neg-
a i e. While in [3] i was al eady es ablished ha such model is no uni e sal, we
ound i in e es ing o in es iga e i s gene a i e powe mo e p ecisely.
Since he numbe o ca alys s emains ini e and does no change h oughou
he compu a ion, his induces a ini e se o “ ule eams” which can be applied
in pa allel in one s ep. The i ual absence o applicabili y condi ions and he
ini eness o he “ eams” hin s a he possibili y o seeing hem as in ege ec o s;
in his case he P sys em i sel can be seen as e ol ing by sequen ially adding such
ec o s (possibly ha ing nega i e componen s) o he con en s o i s memb anes.
Pape [2] compa es his gene al model o ec o addi ion sys ems [5, 9] (adap ed
o allow nega i e ec o componen s [8]) and blind egis e machines [7].
He e we e u n o he pa icula model om [3], discussing he lowe bound o
i s gene a i e powe and gi ing some esul s on he a ian wi h a ge indica ions.
2 P elimina ies
The eade is assumed o be amilia wi h he basic no ions o o mal languages
and memb ane compu ing; see [13] o a comp ehensi e in oduc ion o bo h. We
only ema k ha , as common in memb ane compu ing, mul ise s in O◦=NOa e
ep esen ed by s ings in O∗, keeping in mind ha he o de o symbols is no
ele an .
2.1 Ex ending Mul ise s
To ep esen also nega i e mul iplici ies, mul ise s mus be ex ended. A Z-mul ise ,
allowing in ege mul iplici ies (called a hyb id se in [4]) would be om ZO; i
can be ep esen ed by a s ing in (O∪O−)∗, whe e O−={a−|a∈O}is a
se o symbols ha ep esen s objec s in mul iplici y “nega i e one”. No e ha ,
as opposed o P sys ems wi h ma e -an ima e [1], symbol a−he e is no an
ac ual objec , bu simply a con enien way o ep esen a de ici o a, and he
ac ual mul iplici y o a ep esen ed by a s ing wis |w|a− |w|a−. We also do no
dis inguish be ween no a ions a−kand (a−)k. The supe sc ip −can be used as a
mo phism, p oducing a mul ise wi h opposi e mul iplici ies, e.g., (ak)− ep esen s
he same Z-mul ise as he one in he p e ious sen ence. As he s ings he e a e
only used o ep esen [Z-] mul ise s, we may w i e an equali y sign be ween he
s ings ep esen ing he same [Z-] mul ise . Fo conciseness, le us use he no a ion
O•= (O∪O−)∗. Finally, since i will be always clea om he con ex , we may
call an elemen o O•“mul ise ”, omi ing he wo d “ ep esen ing”. Assuming an
o de is ixed on O, o u∈O•, ec o (|u|a− |u|a−)a∈Ois deno ed by ψO(u); he
subsc ip Omay be omi ed when i is clea om he con ex . This ec o is called
he Pa ihkh image o u.
Pu ely Ca aly ic P Sys ems o e In ege s and Thei Gene a i e Powe 17
2.2 Linea Se s
The linea se gene a ed by a se o ec o s A={ai|1≤i≤d} ⊂ Znand an
o se a0∈Znis de ined as ollows:
hA, a0iN=a0+Xd
i=1 kiai|ki∈N,1≤i≤d.
I he o se a0is he ze o ec o , we will call he co esponding linea se homo-
geneous; we also will use a sho no a ion hAiN=hA, 0iN.
We use he no a ion ZnLINN=hA, a0iN|A∈(Zn)d,a0∈Z, m ∈N, o
e e o he class o all linea se s. Semilinea se s a e de ined as ini e unions o
linea se s. We use he no a ions ZnSLINN o e e o he classes o semilinea
se s o n-dimensional ec o s. In case no es ic ion is imposed on he dimension,
nis eplaced by ∗. We may omi ni n= 1. A ini e union o linea se s which
only di e in he s a ing ec o s is called uni o m semilinea :
ZnSLINU
N=Sb∈BhA, biN|A∈(Zn)d, B ∈(Zn)k, d, k ∈N
=nnb+Pd
i=1 kiai|ki∈N,1≤i≤do|A∈(Zn)d, B ∈(Zn)k, d, k ∈No.
Le us deno e hese se s by hA, BiN.
3 Pu ely Ca aly ic P Sys ems o e In ege s
In pu ely ca aly ic P sys ems o e in ege s he se o objec s is a disjoin union
o ca alys s Cand he egula objec s O. The egula objec s a e allowed o ha e
any in ege mul iplici y, while he ca alys s a e only allowed o appea in a non-
nega i e numbe o copies.
The ules can be o he wo ollowing ypes:
•ca aly ic ules: cu →c , whe e c∈Cand u, ∈O∗;
•ca aly ic ules wi h dissolu ion:cu →c δ, whe e c∈C,u, ∈O∗, and δ6∈
C∪Ois he symbol indica ing memb ane dissolu ion.
The ules applied in pa allel canno in ol e mo e ca alys s han a ailable in he
sys em; he mul iplici ies o egula objec s, on he o he hand, do no in luence
he applicabili y o ules. An applica ion o a ule cu →c in a egion con aining
cw (c∈C,u, ∈O∗,w∈O•p oduces cw(cu)−c =cw (u−), o , in e ms o
ec o s, igno ing he ca alys , ec o ψ(w) + ψ( )−ψ(u) is ep esen ed by he
con en s o ha egion a e he ule has been applied. An applica ion o a ule
cu →c δ p oduces he same e ec , and hen dissol es he enclosing memb ane,
mo ing he con en s o he dissol ed memb ane in o he pa en memb ane.
Pu ely ca aly ic P sys ems o e in ege s e ol e unde he maximally pa -
allel seman ics, so each ca alys en e s exac ly one ule (non-de e minis ically
chosen), unless he gi en egion has no ules associa ed wi h his ca alys . By
18 A. Alhazo , O. Belinghe i, R. F eund, S. I ano , A.E. Po eca, C. Zand on
ZdOZPm(pca k, δ) we deno e he amily o se s o d-dimensional ec o s o in e-
ge s gene a ed by pu ely ca aly ic P sys ems o e in ege s wi h dissolu ion, a mos
mmemb anes and a mos kca alys s. I any o pa ame e s d, m, k is unbounded,
i is eplaced by ∗in he no a ion.
We also use no a ions o ex ended ea u es (lis ed in pa en heses in he no a-
ion o he se s o Z- ec o s gene a ed by he co esponding amilies o P sys ems).
Ta ge indica ions, deno ed by a , allow he non-ca alys s o be sen o a di e en
memb ane. In he igh side o he ules, sending objec ais w i en by (a, a ),
whe e a ∈ {ou }∪{inj|1≤j≤m};jhe e is a label o immedia ely inne
memb ane. In his pape , we may w i e a nin he no a ion o a se o Z- ec o s
gene a ed by a amily o P sys ems; his gene aliza ion e lec s he possibili y o
assign a ge s e en o nega i e mul iplici es o objec s.
Ano he ea u e is mobile ca alys s [10], i.e., a ge s may also be associa ed o
he ca alys s, and hus he ca alys s mo e ac oss he memb ane s uc u e; we de-
no e his ea u e by mpca ksince he sys ems we conside a e pu ely ca aly ic. We
use he plus sign be ween he ea u es o ca aly ic mobili y and dissolu ion when
i is allowed o he same ule o mo e a ca alys and o dissol e he memb ane
cu en ly con aining i .
4 Resul s
4.1 Simpli ica ions and Obse a ions
Fi s , we would like o explici ly allow ules o he o m c→cx, (c∈C,x∈O•),
i.e., he mul ise o egula objec s in he le side being emp y. This does no
change he model, since any Z-mul ise xcan be w i en as u( −), u, ∈O∗, and,
ixing some a∈O,c→cx is equi alen o cau →a . Mo eo e , any ule cu →c
is equi alen o c→cu( −), so i su ices o only conside ules o ypes c→cx
and c→cxδ (c∈C,x∈O•).
Second, no ice ha i is enough o s a wi h a single ca alys in any egion,
because i can pe o m he ole o any numbe o ca alys s, and i mul iple ca -
alys s a e ini ially in he same egion, hey will always s ay in he same egion
(possibly, me ged wi h o he s). Indeed, ake an a bi a y egion o an a bi a y
pu ely ca aly ic P sys em o e in ege s, say, i has ca alys s ci, 1 ≤i≤d, and each
ca alys cihas associa ed ules ci→cixi,j, 1 ≤j≤ni, whe e xi,j ∈O•∪O•δ.
No e ha i none o he ca alys s has associa ed ules, hen hey a e equi alen o
a single ca alys wi h no associa ed ules, so in he ollowing we assume he con-
a y. I some ca alys cihas no associa ed ules, i is hen equi alen o i ha ing
associa ed a single ule ci→ci, i.e., xi,1=λand ni= 1, so in he ollowing we
assume ni≥1 o 1 ≤i≤d. We can now eplace all hese ca alys s by a single
ca alys cha ing associa ed he ollowing se o ules:
{c→cx1,j1· · · xd,jd|1≤ji≤ni,1≤i≤d}.
Pu ely Ca aly ic P Sys ems o e In ege s and Thei Gene a i e Powe 19
On he o he side, no ca alys in some egion is equi alen o one ca alys wi h no
associa ed ules. The e o e, wi hou es ic ing he gene ali y, in he ollowing we
assume ha in he ini ial con igu a ion o an a bi a y pu ely ca aly ic P sys em
o e in ege s, each memb ane egion i, 1 ≤i≤m, con ains p ecisely one ca alys ,
and we can call i ci.
Thi d, no ice ha no in o ma ion en e s memb anes, so he ou e egions can-
no a ec he inne egions in any way. Hence, i he ou pu egion i0is no he
skin, hen only he memb ane subs uc u e inside i0, including i0is ele an o he
esul , and o he memb anes a e i ele an and may be emo ed wi hou a ec ing
he esul , making i0 he skin (unless some ule in some emo ed memb ane had
applicable ules, bu could ne e be dissol ed, in which case he gene a ed se o
ec o s is emp y, which is a degene a e case). So in he ollowing, we assume ha
he ou pu egion is always he skin.
Fou h, e e y elemen a y memb ane ha ing no ules associa ed o he ca alys s
a ailable he e may be emo ed om he sys em wi hou a ec ing he esul (unless
i is he ou pu memb ane, in which case a single on is gene a ed, which is a
degene a e case), so in he ollowing we assume ha each elemen a y memb ane
has some applicable ules. Clea ly, he P sys em will no each he hal ing un il
his memb ane is dissol ed.
Conside his easoning s a ing om he elemen a y memb anes ou side, by
induc ion. Take any non-elemen a y memb ane iwhich becomes elemen a y du ing
a compu a ion. Assume iis no dissol ed (i.e., i has no ules associa ed o any o
he ca alys s ha we e placed wi hin he memb ane subs uc u e inside i, including
i), bu i is no he ou pu memb ane. Then all he compu a ion in he memb ane
subs uc u e inside i, including i, does no con ibu e o he esul , and can be
emo ed om he sys em wi hou a ec ing he esul .
As a summa y o he ou h obse a ion, wi hou es ic ing he gene ali y
(excep , possibly he degene a e cases gene a ing he emp y se o some single on),
we may assume ha any pu ely ca aly ic P sys em o e in ege s has applicable
ules associa ed o all elemen a y memb anes, and all memb anes excep he skin
mus be dissol ed a some momen du ing he compu a ion.
Finally, o e e y egion excep he skin, a ca alys ciwi hou associa ed ules
is equi alen o a ca alys wi h a ule ci→ci. Hence, wi hou es ic ing he
gene ali y, we may assume ha he ca alys s a e ne e idle be o e he hal ing is
eached. Clea ly, (excluding he degene a e case gene a ing he emp y se ), he
skin should ha e no ules associa ed o any ca alys o he sys em.
We would like o no e ha e en wi hou p uning he memb ane s uc u e by
emo ing memb ane subs uc u es no con ibu ing o he esul , he memb ane
s uc u e ob ained a hal ing (i a all eachable) is unique.
We ecall ha in [2], he ollowing gene aliza ion app oach is aken: The e is
a ini e numbe o eachable memb ane s uc u es. These could be used as s a es
o a sequen ial P sys em, which may be ob ained, sepa a ely o each memb ane
s uc u e, by combining he beha io o all ca alys s in all egions o he P sys em.
Indeed, ha ing ixed a eachable memb ane s uc u e, we know which memb anes

20 A. Alhazo , O. Belinghe i, R. F eund, S. I ano , A.E. Po eca, C. Zand on
ha e been dissol ed, and hus he esul ing loca ion o each ca alys . Then, o each
ca alys , associa ed ules in i s cu en loca ion a e conside ed and combined, sim-
ila ly o he second obse a ion abo e, bu globally. Ha ing ob ained a sequen ial
sys em, he ca alys is no longe needed. Then, in [2] i was shown ha such a
gene aliza ion is no hing else bu a sequen ial blind ec o addi ion sys em wi h
s a es, and i was claimed ha i cha ac e izes p ecisely he amily o all semilinea
ec o s o in ege s.
Indeed, in his way any pu ely ca aly ic P sys em o e in ege s can be subs i-
u ed by a sequen ial blind ec o addi ion sys em wi h s a es, so he uppe bound
o he amily o all semilinea se s o ec o s o in ege s, o , equi alen ly, he amily
o all in ege ec o se s, gene a ed by blind egis e machines, holds. Howe e , he
e e se is no necessa ily ue, i.e., i does no ollow ha o any sequen ial blind
ec o addi ion sys em wi h s a es he e would exis an equi alen pu ely ca aly ic
P sys em o e in ege s.
Ano he esul in [2] has been ob ained o in ege ec o addi ion P sys ems,
namely Theo em 5. Tha model has been shown o cha ac e ize exac ly he uni o m
semilinea se s. Howe e , since in he model o in ege ec o addi ion P sys ems,
as opposed o pu ely ca aly ic P sys ems o e in ege s, he e is no concep o a
ca alys , dissol ing a memb ane only disables ules o ha egion, wi hou enabling
ules ha , in pu ely ca aly ic P sys ems o e in ege s, a e con ained in he pa en
egion and associa ed o he ca alys s ha we e in he dissol ed egion. Hence,
he cha ac e iza ion om Theo em 5 o [2] has no di ec implica ion on he powe
o pu ely ca aly ic P sys ems o e in ege s.
The e o e, a his poin in he p esen pape we would like o de ini ely de ia e
in o he pa icula i ies o how dissolu ion a ec s he compu a ion, and he lowe
bounds.
4.2 Gene a i e Powe
We ecall ha we discuss he amily o in ege ec o se s gene a ed by pu ely
ca aly ic P sys ems o e in ege s, wi h he usual hal ing condi ion.
Since he ou pu egion canno be dissol ed by de ini ion and any o he appli-
cable ule can ne e be s opped, single-memb ane pu ely ca aly ic P sys ems o e
in ege s a e degene a e:
ZdOZP1(pca ∗, δ) = {∅} ∪ {{ } | ∈Zd}.
Fo simplici y, we will no men ion hese degene a e cases while conside ing mul-
iple memb anes.
Wi h wo memb anes, a cha ac e iza ion is s ill s aigh o wa d:
ZdOZP2(pca ∗, δ) = ZdSLINU
N.
Indeed, le Abe he ini e se o ec o s co esponding o he non-dissol ing ules
in he elemen a y memb anes, and le Bbe he ini e se o sums o wo ec o s:
Pu ely Ca aly ic P Sys ems o e In ege s and Thei Gene a i e Powe 21
he one co esponding o he ini ial con igu a ion and ec o s co esponding o he
dissol ing ules in he elemen a y memb ane; he skin should ha e no ules. I he
ca alys in he elemen a y memb ane is c2, hen he co espondence men ioned
abo e is c2→c2x↔ψ(x), and simila ly wi h dissolu ion. An a bi a y compu a-
ion o a P sys em consis s o an a bi a y numbe o applica ions o non-dissol ing
ules and one applica ion o a dissol ing ule. Hence, he esul ing ec o sums up
om he “ini ial” ec o , one a bi a y “dissol ing” ec o , and an a bi a y linea
combina ion o “non-dissol ing” ec o s.
I is wo h no ing ha , by a simila easoning, o a P sys em wi h mul iple
memb anes, i he ch onological o de o dissol ing memb anes is ixed, he esul is
s ill ZdSLINU
N. Indeed, each combina ion o ules (one o each ca alys ) yields one
ec o , so all such possible combina ions o non-dissol ing ules yield a ini e se
o ec o s, and mul iple non-dissol ing s eps yield a linea se gene a ed by hese
ec o s. Thus, o e he whole compu a ion he esul sums up om he ini ial
con igu a ion, a ini e numbe o dissolu ion ec o s, and a ini e numbe o linea
se s co esponding o he memb ane s uc u es eached du ing ha compu a ion.
Since he o al numbe o ch onological o de s o dissol ing memb anes is bounded,
he known esul al eady ollows:
ZdOZP∗(pca ∗, δ)⊆ZdSLINN.
E en wi h h ee memb anes, in case wo o hem a e elemen a y, he powe o
such pu ely ca aly ic P sys ems o e in ege s is s ill ZdSLINU
N, bu o a di e en
eason: each elemen a y memb ane con ibu es wi h i s uni o m semilinea se ,
and a sum o wo uni o m semilinea se s is s ill uni o m semilinea .
Le us now examine a P sys em wi h h ee nes ed memb anes – he minimal
numbe o ob ain a se which is no in ZdSLINU
N. Le he ec o ob ained by
joining he ini ial con en s o all memb anes be a, he se o non-dissol ing ec o s
o he elemen a y memb ane be A3, he se o dissol ing ec o s o he elemen a y
memb ane be B3, he se s o non-dissol ing and dissol ing ec o s in he middle
memb ane associa ed o ca alys c2a e A2and B2, and he simila se s associa ed
o ca alys c3(which will a i e om he elemen a y memb ane) a e Aand B. Le
us see wha he esul ing ec o se is buil om, besides a.
A non-dissol ing compu a ion in h ee memb anes adds a each s ep (an ele-
men o ) A3 o he elemen a y memb ane and (an elemen o ) A2 o he middle
memb ane. E en ually all objec s will a i e o he skin, so he h ee-memb ane
phase o he compu a ion will con ibu e by (an a bi a y elemen o ) hA2+A3iN.
Then he e a e wo possibili ies. I memb ane 2 is dissol ed i s , hen he
sys em con inues compu ing by only applying he ules in memb ane 3, and e en-
ually dissol ing memb ane 3, yielding B2+hA3iN+B3. Howe e , i memb ane
3 is dissol ed i s , hen bo h ca alys s a e ac i e in memb ane 2, e en ually dis-
sol ing i , yielding B3+hA2+AiN+ (B2+A∪A2+B∪A+B). The exp ession
in pa en heses co esponds o applying a leas one dissol ing ule. The e o e, he
se o in ege ec o s gene a ed by such a pu ely ca aly ic P sys em o e in ege s
wi h h ee nes ed memb anes is
22 A. Alhazo , O. Belinghe i, R. F eund, S. I ano , A.E. Po eca, C. Zand on
M=a+B3+hA2+A3iN+B2+hA3iN∪ hA2+AiN+B2+A∪A2+B∪B2+B,
and he powe o all h ee-memb ane pu ely ca aly ic P sys ems o e in ege s,
no ing ha he powe o he nes ed case subsumes he powe o he case wi h wo
elemen a y memb anes, is
ZdOZP1(pca ∗, δ) = {M|a∈Zd, A2, A3, B2, B3, A, B ∈F IN(Zd)},
whe e Mis he exp ession abo e. Un o una ely, i is no ob ious wha can be
simpli ied in i , excep B3can subsume a. So we y o analyze i in de ails,
possibly going in o pa icula cases.
All e ms in he exp ession Ma e bounded excep h ee: hA3+A2iN,hA3iN
and hA+A2iN. These e ms a e no independen , e en hough A2,A3and Aa e
h ee independen ini e se s o ec o s. I is, howe e , possible o sepa a e hem
in a pa icula case when |A3|= 1, choosing A2=−A3and A=C−A2. Since
A3is a single on, he iden i y A3−A3={0}holds, so he h ee unbounded e ms
become h{0}iN,hA3iNand hCiN, so we a e ge ing close o ob aining a union o
wo pa icula linea (o e en uni o m semilinea ) se s wi h di e en base ec o s.
Indeed, i we choose a=0,B3={0},B2={0},B={0}and A3={e},
exp ession Msimpli ies o h{e}iN∪hCiN+(C+{e}∪{0}), which can be ew i en
as h{e}iN∪ hCiN∪ {e} hCiN.
Al e na i ely, o a oid dealing wi h he union o h ee cases when memb ane
2 is di ided las , i we choose B2=A2and B=A, hen he las pa en hesis in
he gene al exp ession o se Mbecomes simply A2+A=C. Choosing a=0,
B3={0}, and A3={e}, exp ession Msimpli ies o h{e}iN− {e}∪hCiN+C.
Since 0∈ h{e}iN− {e}and hCiN+C∪ {0}=hCiN, in his case we can ew i e
M o
−{e} ∪ h{e}iN∪ hCiN,
which is a union o any wo homogeneous linea se s, such ha he i s one has
only one gene a o , uni ed wi h he opposi e ec o o ha gene a o . Hence,
ZdOZPn(ca , δ))ZdSLINU
N, n ≥3.
Wha i B=∅, i.e., ca alys c3has no associa ed dissolu ion ules in egion 2?
Then he gene al exp ession o se Mis immedia ely simpli ied o
M=a+B2+B3+hA2+A3iN+ (hA3iN∪ hA2+AiN+A),
and in ou case o A3={e},A2=−{e}and A=C+{e},Mbecomes
a+B2+B3+ (h{e}iN∪ hCiN+C+{e}),
and choosing a+B2+B3={−e}, and no icing ha C0 imes is co e ed by e0
imes and hCiN+C∪{0}=hCiN, we simpli y M o {−e} ∪h{e}iN∪ hCiN, i.e., an
“almos clean union” we al eady ob ained be o e. Finally, we no ice ha we can
equi alen ly w i e i as
h{e},−eiN∪ hCiN.
Con inuing he cu en app oach wi h mo e memb anes would only esul in mo e
cases.
Pu ely Ca aly ic P Sys ems o e In ege s and Thei Gene a i e Powe 23
4.3 Communica ion
We would like o ema k ha adding a ge indica ions o he egula objec s
should no inc ease he powe o pu ely ca aly ic P sys ems o e in ege s. Indeed,
looking a a pu ely ca aly ic P sys em o e in ege s, i is easily decidable which
memb anes will e en ually be dissol ed. Hence, he only ques ion is whe he he
con en s o a egion speci ied by a ge , a e possible dissolu ions, will be in he
ou pu . The e is no need o examine he u u e o a mo ed egula objec , since
he esou ces in pu ely ca aly ic P sys ems o e in ege s a e unbounded, and we
can iew his copy o a mo ed objec as s aying in ha egion un il he end o he
compu a ion.
Howe e , i also he ca alys s a e allowed o ha e a ge indica ions associa ed,
i does make a di e ence. We claim he ollowing cha ac e iza ions.
ZdOZP∗(mpca k, a n) = ZdSLINN, k ≥1,
ZdOZP∗(mpca k+δ) = ZdSLINN, k ≥1,
ZdOZP∗(mpca ∗, δ) = ZdSLINN,
The uppe bound in ei he case is easy o see because he numbe o possible
a angemen s o ca alys s ac oss he gi en memb ane s uc u e (and any possible
s uc u es ob ained om i by memb ane dissolu ions) is bounded. Hence, pu ely
ca aly ic P sys ems o e in ege s wi h mobile ca alys s a e s ill no mo e powe ul
han blind ec o -addi ion sys ems wi h s a es, which cha ac e ize Z∗SLINN, see
[2]. We now p oceed o ⊇inclusions.
Conside an a bi a y semilinea se S1≤i≤mhAi, biiN, whe e o each i, 1 ≤i≤
m,Aiis a ini e se , Ai∪ {bi} ⊆ Zd. We cons uc he ollowing pu ely ca aly ic
P sys em o e in ege s
Π1= (O, C, µ, w1,· · · , w2m+1, R1,· · · , R2m+1, i0= 1) whe e
O={ai|1≤i≤d}, C ={c},
µ= [ [ [ ]m+2 ]2· · · [ [ ]2m+1 ]m+1 ]1,
w1=c, wi+1 =λ, 1≥i≥2m,
R1={c→(c, ini+1) i|1≤i≤m, ψ( i) = bi},
Ri+1 ={c→c( , ou )|ψ( )∈Ai}∪{c→(c, inm+i+1)},1≤i≤m,
Rm+i+1 =∅,1≤i≤m.
The wo k o Π1consis s o a non-de e minis ic choice o i- h linea se o gene a e,
by mo ing ca alys cin o memb ane i+ 1 and p oducing bi. A e sending o he
skin an a bi a y combina ion o ec o s om Ai, he ca alys en e s memb ane
m+i+ 1 and he sys em hal s.
The sys em Π2is ob ained om Π1by eplacing he se s Ri+1 o ules, 1 ≤
i≤m, by
{c→c |ψ( )∈Ai}∪{c→(c, inm+i+1)δ}.