The Role o he En i onmen in
Tissue P Sys ems wi h Cell Di ision
Ma io J. P´e ez-Jim´enez1, Agus ´ın Riscos-N´u˜nez1, Miquel Rius-Fon 2,
F ancisco J. Rome o-Campe o1
1Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se ille
A da. Reina Me cedes s/n, 41012 Se illa, Spain
E-mail: [email p o ec ed], [email p o ec ed], [email p o ec ed]
2Depa men o Applied Ma hema ics IV
Uni e si a Poli ´ecnica de Ca alunya, Spain
E-mail: [email p o ec ed]
Summa y. Classical issue P sys ems wi h cell di ision ha e a special alphabe whose
elemen s appea a he ini ial configu a ion o he sys em in an a bi a y la ge numbe
o copies. These objec s a e sha ed in a dis inguished place o he sys em, called he en-
i onmen . Besides, he abili y o hese compu ing de ices o ha e infini e copies o some
objec s has been widely exploi ed in he design o efficien solu ions o compu a ionally
ha d p oblems.
This pape deals wi h compu a ional aspec s o issue P sys ems wi h cell di ision
whe e he e is no an en i onmen ha ing he p ope y men ioned abo e. Specifically,
we es ablish he ela ionships be ween he polynomial complexi y class associa ed wi h
issue P sys ems wi h cell di ision and wi h o wi hou en i onmen . As a consequence,
we p o e ha i is no necessa y o ha e infini e copies o some objec s a he ini ial
configu a ion in o de o sol e NP–comple e p oblems in an efficien way.
Key wo ds:Memb ane Compu ing, Tissue P Sys ems, Cell Di ision, En i onmen
o a issue, Compu a ional Complexi y.
1 P elimina ies
An alphabe ,Γ, is a non–emp y se whose elemen s a e called symbols. An o de ed
fini e sequence o symbols is a s ing o wo d. I uand a e s ings o e Γ, hen so
is hei conca ena ion u , ob ained by jux aposi ion, ha is, w i ing uand one
a e he o he . The numbe o symbols in a s ing uis he leng h o he s ing and
i is deno ed by |u|. As usual, he emp y s ing (wi h leng h 0) will be deno ed by
λ. The se o all s ings o e an alphabe Γis deno ed by Γ∗. In algeb aic e ms, Γ∗
90 M.J. P´e ez-Jim´enez e al.
is he ee monoid gene a ed by Γunde he ope a ion o conca ena ion. Subse s,
fini e o infini e, o Γ∗a e e e ed o as languages o e Γ.
The se o symbols occu ing in a s ing u∈Γ∗is deno ed by alph(u).
The Pa ikh ec o associa ed wi h a s ing u∈Γ∗wi h espec o he alphabe
Σ={a1, . . . , a } ⊆ Γis ΨΣ(u) = (|u|a1, . . . , |u|a ), whe e |u|aideno es he numbe
o ocu ences o symbol aiin s ing u. This is called he Pa ikh mapping associa ed
wi h Σ. No ice ha , in his defini ion, he o de ing o he symbols om Σis
ele an . I Σ1={ai1, . . . , ai } ⊆ Γ, hen we define ΨΣ1(u)=(|u|ai1, . . . , |u|ai ),
o each u∈Γ∗.
Amul ise mo e a se Ais a pai (A, ) whe e :A→Nis a mapping. I
m= (A, ) is a mul ise hen i s suppo is defined as supp(m) = {x∈A| (x)>
0}. A mul ise is emp y ( esp. fini e) i i s suppo is he emp y se ( esp. a fini e
se ). I m= (A, ) is a fini e mul ise o e Aand supp(m) = {a1, . . . , ak}, hen
i will be deno ed as m={a (a1)
1, . . . , a (ak)
k}. Tha is, supe sc ip s indica e he
mul iplici y o each elemen , and i (x) = 0 o x∈A, hen elemen xis omi ed.
A fini e mul ise m={a (a1)
1, . . . , a (ak)
k}can also be ep esen ed by he s ing
a (a1)
1. . . a (ak)
ko e he alphabe {a1, . . . , ak}. Ne e heless, all pe mu a ions o
his s ing iden i y he same mul ise mp ecisely. Th oughou his pape , we speak
abou “ he fini e mul ise m” whe e mis a s ing, meaning “ he fini e mul ise
ep esen ed by he s ing m”. I m1= (A, 1), m2= (A, 2) a e mul ise s o e A,
hen we define he union o m1and m2as m1+m2= (A, g), whe e g= 1+ 2,
ha is, g(a) = 1(a) + 2(a), o each a∈A.
Fo any se s Aand B he ela i e complemen A Bo Bin Ais defined as
ollows: A B={x∈A|x /∈B}.
Finally, o any se Awe deno e |A| he ca dinal (numbe o elemen s) o A, as
usual.
In wha ollows, we assume he eade is al eady amilia wi h he basic no ions
and e minology o P sys ems. Fo de ails, see [4].
2 Tissue P Sys ems wi h communica ion ules
De ini ion 2.1 A issue P sys em wi h communica ion ules o deg ee q≥1is a
uple Π= (Γ, E,M1, . . . , Mq,R, iou ), whe e:
1. Γis a fini e alphabe whose elemen s a e called objec s;
2. E ⊆ Γ;
3. M1, . . . , Mqa e s ings o e Γ, ep esen ing fini e mul ise s o objec s;
4. Ris a fini e se o communica ion ules o he o m (i, u/ , j), o i, j ∈
{0,1,2, . . . , q}, i =j,u, ∈Γ∗,|u|+| |>0;
5. iou ∈ {0,1,2, . . . , q}.
A issue P sys em wi hou en i onmen is a issue P sys em such ha E=∅. In
his case, alphabe Ecan be emo ed om he uple.
The Role o he En i onmen in Tissue P Sys ems wi h Cell Di ision 91
A issue P sys em wi h communica ion ules Π= (Γ, E,M1, . . . , Mq,R, iou ),
o deg ee q≥1 can be iewed as a se o qcells, labelled by 1, . . . , q, wi h an
en i onmen labelled by 0 such ha : (a) M1, . . . , Mq ep esen he fini e mul ise s
o objec s ini ially placed in he qcells o he sys em; (b) Eis he se o objec s
ini ially loca ed in he en i onmen o he sys em, all o hem a ailable in an
a bi a y numbe o copies; and (c) iou ∈ {0,1,2, . . . , q} ep esen s a dis inguished
cell o he en i onmen which will encode he ou pu o he sys em. We use he
e m egion i(0 ≤i≤q) o e e cell iin he case 1 ≤i≤qand o e e he
en i onmen in he case i= 0.
When applying a ule (i, u/ , j), he objec s o he mul ise ep esen ed by u
a e sen om egion i o egion jand, simul aneously, he objec s o mul ise
a e sen om egion j o egion i. The leng h o he communica ion ule (i, u/ , j)
is defined as |u|+| |.
A communica ion ule (i, u/ , j) is called a sympo ule i u=λo =λ. A
sympo ule (i, u/λ, j), wi h i= 0, j = 0, p o ides a i ual a c om cell i o cell
j. A communica ion ule (i, u/ , j) is called an an ipo ule i u=λand =λ.
An an ipo ule (i, u/ , j), wi h i= 0, j = 0, p o ides wo a cs: one om cell i
o cell jand ano he one om cell j o cell i. Thus, e e y issue P sys em has an
unde lying di ec ed g aph whose nodes a e he cells o he sys em and he a cs
a e ob ained om communica ion ules. In his con ex , he en i onmen can be
conside ed as a i ual node o he g aph such ha i s connec ions a e defined by
communica ion ules o he o m (i, u/ , j), wi h i= 0 o j= 0.
The ules o a sys em like he one abo e a e used in a non-de e minis ic max-
imally pa allel manne as i is cus oma y in memb ane compu ing. A each s ep,
all cells which can e ol e mus e ol e in a maximally pa allel way (a each s ep
we apply a mul ise o ules which is maximal, no u he applicable ule can be
added).
An ins an aneous desc ip ion o a configu a ion a any ins an o a issue P
sys em wi h communica ion ules is desc ibed by all mul ise s o objec s o e Γ
associa ed wi h all he cells p esen in he sys em, and he mul ise o objec s o e
Γ− E associa ed wi h he en i onmen a ha momen . Bea ing in mind ha
he objec s om Eha e infini e copies in he en i onmen , hey a e no p ope ly
changed along he compu a ion. The ini ial configu a ion is (M1,··· ,Mq;∅). A
configu a ion is a hal ing configu a ion i no ule o he sys em is applicable o i .
Le us fix a issue P sys em wi h communica ion ules Π. We say ha con-
figu a ion C1yields configu a ion C2in one ansi ion s ep, deno ed C1⇒ΠC2, i
we can pass om C1 o C2by applying he ules om R ollowing he p e ious
ema ks. A compu a ion o Πis a (fini e o infini e) sequence o configu a ions
such ha :
1. he fi s e m o he sequence is he ini ial configu a ion o he sys em;
2. each non-ini ial configu a ion o he sequence is ob ained om he p e ious
configu a ion by applying he ules o he sys em in a maximally pa allel man-
ne wi h he es ic ions p e iously men ioned; and
92 M.J. P´e ez-Jim´enez e al.
3. i he sequence is fini e (called hal ing compu a ion), hen he las e m o he
sequence is a hal ing configu a ion.
All compu a ions s a om an ini ial configu a ion and p oceed as s a ed abo e;
only hal ing compu a ions gi e a esul , which is encoded by he objec s p esen
in he ou pu egion iou in he hal ing configu a ion.
We deno e by Comp(Π) he se o compu a ions o he issue P sys em Π.
I C={Ci}i< +1 o Π( ∈N) is a hal ing compu a ion, hen he leng h o C
is , ha is, he numbe o non-ini ial configu a ions which appea in he fini e
sequence C. We deno e i by |C|. We also deno e by Ci(j) he con en s o cell ja
configu a ion Ci.
3 Tissue P Sys ems wi h Cell Di ision
Cell di ision is an elegan p ocess ha enables o ganisms o g ow and ep oduce.
Mi osis is a p ocess o cell di ision which esul s in he p oduc ion o wo daugh e
cells om a single pa en cell. Daugh e cells a e iden ical o one ano he and o he
o iginal pa en cell. Th ough a sequence o s eps, he eplica ed gene ic ma e ial
in a pa en cell is equally dis ibu ed o wo daugh e cells. While he e a e some
sub le diffe ences, mi osis is ema kably simila ac oss o ganisms.
Be o e a di iding cell en e s mi osis, i unde goes a pe iod o g ow h whe e he
cell eplica es i s gene ic ma e ial and o ganelles. Replica ion is one o he mos
impo an unc ions o a cell. DNA eplica ion is a simple and p ecise p ocess ha
c ea es wo comple e s ands o DNA (one o each daugh e cell) whe e only one
exis ed be o e ( om he pa en cell).
Le us ecall ha he model o issue P sys ems wi h cell di ision is based on
he cell-like model o P sys ems wi h memb anes di ision [3]. In hese models, he
cells a e no pola ized; he cells ob ained by di ision ha e he same labels as he
o iginal cell, and i a cell is di ided, i s in e ac ion wi h o he cells o wi h he
en i onmen is locked du ing he di ision p ocess. In some sense, his means ha
while a cell is di iding i closes i s communica ion channels.
De ini ion 3.1 A issue P sys em wi h cell di ision o deg ee q≥1is a uple
Π= (Γ, E,M1, . . . , Mq,R, iou ), whe e:
1. Γis a fini e alphabe whose elemen s a e called objec s;
2. E ⊆ Γ;
3. M1, . . . , Mqa e s ings o e Γ, ep esen ing fini e mul ise s o objec s;
4. Ris a fini e se o ules o he ollowing o ms:
(a) Communica ion ules:(i, u/ , j), o i, j ∈ {0,1,2, . . . , q}, i =j,u, ∈Γ∗,
|u|+| |>0;
(b) Di ision ules:[a]i→[b]i[c]i, whe e i∈ {1,2, . . . , q},i=iou and a, b, c ∈
Γ;
5. iou ∈ {0,1,2, . . . , q}.
The Role o he En i onmen in Tissue P Sys ems wi h Cell Di ision 93
A issue P sys em wi h cell di ision is a issue P sys em wi h communica ion ules
whe e also di ision ules a e allowed. When applying a di ision ule [a]i→[b]i[c]i,
unde he influence o objec a, he cell wi h label iis di ided in o wo cells wi h
he same label; in he fi s copy, objec ais eplaced by objec b, in he second
one, objec ais eplaced by objec c; all he o he objec s esiding in cell ia e
eplica ed and copies o hem a e placed in he wo new cells. The ou pu cell iou
canno be di ided.
The ules o a issue P sys em wi h cell di ision a e applied in a non-
de e minis ic maximally pa allel manne as i is cus oma y in memb ane compu -
ing. A each s ep, all cells which can e ol e mus e ol e in a maximally pa allel
way (a each s ep we apply a mul ise o ules which is maximal, no u he ap-
plicable ule can be added), wi h he ollowing impo an ema k: i a cell di ides,
hen he di ision ule is he only one which is applied o ha cell a ha s ep; he
objec s inside ha cell do no e ol e by means o communica ion ules. In o he
wo ds, be o e di ision a cell in e up s all i s communica ion channels wi h he
o he cells and wi h he en i onmen . The new cells esul ing om di ision will
in e ac wi h o he cells o wi h he en i onmen only a he nex s ep – p o iding
ha hey do no di ide once again. The label o a cell p ecisely iden ifies he ules
which can be applied o i .
4 Recognize Tissue P Sys ems
Le us ecall ha a decision p oblem is a pai (IX, θX) whe e IXis a language o e
a fini e alphabe (whose elemen s a e called ins ances) and θXis a o al boolean
unc ion o e IX. Many abs ac p oblems a e no decision p oblems. Fo example,
in combina o ial op imiza ion p oblems some alue mus be op imized (minimized
o maximized). In o de o deal wi h such p oblems, hey can be ans o med in o
oughly equi alen decision p oblems by supplying a a ge / h eshold alue o he
quan i y o be op imized, and hen asking whe he his alue can be a ained.
A na u al co espondence be ween decision p oblems and languages can be
es ablished as ollows. Gi en a decision p oblem X= (IX, θX), i s associa ed
language is LX={w∈IX:θX(w) = 1}. Con e sely, gi en a language L, o e an
alphabe Γ, i s associa ed decision p oblem is XL= (IXL, θXL), whe e IXL=Γ∗,
and θXL={(x, 1) : x∈L}∪{(x, 0) : x /∈L}. The sol abili y o decision p oblems
is defined h ough he ecogni ion o he languages associa ed wi h hem.
In o de o s udy he compu ing efficiency, he no ions om classical compu a-
ional complexi y heo y a e adap ed o memb ane compu ing, and a special class
o cell-like P sys ems is in oduced in [7]: ecognize P sys ems (called accep ing
P sys ems in a p e ious pape [6]). Fo issue P sys ems, wi h he same idea as
ecognize cell-like P sys ems, ecognize issue P sys ems is in oduced in [5].
De ini ion 4.1 A ecognize issue P sys em wi h cell di ision o deg ee q≥1is
a uple Π= (Γ, Σ, E,M1,...,Mq,R, iin, iou ), whe e:

94 M.J. P´e ez-Jim´enez e al.
•(Γ, E,M1, . . . , Mq,R, iou )is a issue P sys em wi h cell di ision o deg ee
q≥1, as defined in he p e ious sec ion.
•The wo king alphabe Γhas wo dis inguished objec s yes and no, a leas one
copy o hem p esen in some ini ial mul ise s M1, . . . , Mq, bu none o hem
is p esen in E.
•Σis an (inpu ) alphabe s ic ly con ained in Γsuch ha E ∩ Σ=∅.
• M1, . . . , Mqa e s ings o e Γ Σ.
•iin ∈ {1, . . . , q}is he inpu cell.
•The ou pu egion iou is he en i onmen . In he case o issue wi hou en i-
onmen , iou is a dis inguished cell, ha is iou ∈ {1, . . . , q}.
•All compu a ions hal .
•I Cis a compu a ion o Π, hen ei he objec yes o objec no (bu no bo h)
mus ha e been eleased in o he en i onmen , and only a he las s ep o he
compu a ion.
Fo each mul ise mo e Σ, he compu a ion o he sys em Πwi h inpu ms a s
om he configu a ion o he o m (M1,M2, . . . , Miin +m, . . . , Mq;∅), ha is,
he inpu mul ise mhas been added o he con en s o he inpu cell iin, and we
deno e i by Π+m. The e o e, we ha e an ini ial configu a ion associa ed wi h
each inpu mul ise m(o e he inpu alphabe Σ) in his kind o sys ems.
Gi en a ecognize issue P sys em wi h cell di ision, and a hal ing compu a ion
C={Ci}i< +1 o Π( ∈N), we define he esul o Cas ollows:
Ou pu (C) = 






yes,i Ψ{yes,no}(M ,iou ) = (1,0) ∧
Ψ{yes,no}(Mi,iou ) = (0,0) o i= 0, . . . , −1
no,i Ψ{yes,no}(M ,iou ) = (0,1) ∧
Ψ{yes,no}(Mi,iou ) = (0,0) o i= 0, . . . , −1
whe e Ψis he Pa ikh mapping, and Mi,iou is he mul ise o e Γ E associa ed
wi h he ou pu egion a he configu a ion Ci, in pa icula , M ,iou is he mul ise
o e Γ E associa ed wi h he ou pu egion a he hal ing configu a ion C .
We say ha a compu a ion Cis an accep ing compu a ion ( espec i ely, ejec -
ing compu a ion) i Ou pu (C) = yes ( espec i ely, Ou pu (C) = no), ha is, i
objec yes ( espec i ely, objec no) appea s in he ou pu egion associa ed wi h
he co esponding hal ing configu a ion o C, and nei he objec yes no no appea s
in he ou pu egion associa ed wi h any non–hal ing configu a ion o C.
Le us no ice ha i a ecognize issue P sys em
Π= (Γ, Σ, E,M1, . . . , Mq,R, iin, iou )
has a ule o he ype (i, λ/u, 0) hen alph(u)∩(Γ E)=∅, because on he con a y
all compu a ions o Πwould be non hal ing.
Fo each na u al numbe k≥1, we deno e by TDC(k) he class o ecognize
issue P sys ems wi h cell di ision and wi h communica ion ules o leng h a mos
k. In he case o issue P sys ems wi hou en i onmen , we deno e by
TDC(k)
he class o ecognize issue P sys ems wi h cell di ision and wi h communica ion
ules o leng h a mos k.
The Role o he En i onmen in Tissue P Sys ems wi h Cell Di ision 95
5 Polynomial Complexi y Classes o Tissue P sys ems
Nex , we define wha sol ing a decision p oblem in he amewo k o issue P
sys ems in a uni o m and efficien way means. Bea ing in mind ha hey p o ide
de ices wi h a fini e desc ip ion, a nume able amily o issue P sys ems will be
necessa y in o de o sol e a decision p oblem.
De ini ion 5.1 We say ha a decision p oblem X= (IX, θX)is sol able in a
uni o m way and polynomial ime by a amily Π={Π(n)|n∈IN}o ecog-
nize issue P sys ems (wi h sympo /an ipo ules, wi h cell di ision o wi h cell
sepa a ion) i he ollowing holds:
•The amily Πis polynomially uni o m by Tu ing machines, ha is, he e exis s
a de e minis ic Tu ing machine wo king in polynomial ime which cons uc s
he sys em Π(n) om n∈IN.
•The e exis s a pai (cod, s)o polynomial- ime compu able unc ions o e IX
such ha :
− o each ins ance u∈IX,s(u)is a na u al numbe , and cod(u)is an inpu
mul ise o he sys em Π(s(u));
− o each n∈IN,s−1(n)is a fini e se ;
− he amily Πis polynomially bounded wi h ega d o (X, cod, s), ha is,
he e exis s a polynomial unc ion p, such ha o each u∈IXe e y com-
pu a ion o Π(s(u)) wi h inpu cod(u)is hal ing and i pe o ms a mos
p(|u|)s eps;
− he amily Πis sound wi h ega d o (X, cod, s), ha is, o each u∈IX,
i he e exis s an accep ing compu a ion o Π(s(u)) wi h inpu cod(u), hen
θX(u) = 1;
− he amily Πis comple e wi h ega d o (X, cod, s), ha is, o each u∈IX,
i θX(u)=1, hen e e y compu a ion o Π(s(u)) wi h inpu cod(u)is an
accep ing one.
F om he soundness and comple eness condi ions abo e we deduce ha e e y
P sys em Π(n) is confluen , in he ollowing sense: e e y compu a ion o a sys em
wi h he same inpu mul ise mus always gi e he same answe .
Le Rbe a class o ecognize issue P sys ems. We deno e by PMCR he
se o all decision p oblems which can be sol ed in a uni o m way and polynomial
ime by means o amilies o sys ems om R. The class PMCRis closed unde
complemen and polynomial– ime educ ions [6].
Nex , we p o e a echnical esul conce ning ecognize issue P sys ems.
Lemma 5.2 Le Π={Π(n)|n∈IN}a amily o ecognize issue P sys ems
sol ing a decision p oblem X= (IX, θX)in polynomial ime acco ding o he p e-
ious defini ion. Le (cod, s)a polynomial encoding associa ed wi h ha solu ion.
Le (n)be a polynomial unc ion such ha o each u∈IXe e y compu a ion
o Π(s(u)) + cod(u)is hal ing and i pe o ms a mos (|u|)s eps. Then, he e
exis s a polynomial unc ion p(n)such ha o each ins ance u∈IX,2p(|u|)is an
96 M.J. P´e ez-Jim´enez e al.
uppe bound o he numbe o objec s om Ewhich a e mo ed om he en i on-
men o all cells o he sys em Π(s(u))+cod(u)by communica ion ules along any
compu a ion.
P oo : Le u∈IXbe an ins ance o Xand
Π(s(u)) + cod(u) = (Γ, Σ, E,M1, . . . , Mq,R, iin, iou )
Le k∈IN be such ha Π(s(u)) + cod(u)∈TDC(k). Le M=|M1+· · · +Mq|.
Then, any compu a ion o Π(s(u)) + cod(u) pe o ms, a mos , (|u|) ansi ion
s eps. Le C= (C0,C1,...,Cm), 0 ≤m≤ (|u|), be a compu a ion o Π. Fo each
, 0 ≤ ≤mand i, 1 ≤i≤q, we deno e by C (i) he mul ise o objec s o e Γ
in cell ia ime . We also deno e C (0) he mul ise o objec s o e Γ E in he
en i onmen a ime .
Le us suppose ha we apply only communica ion ules a mconsecu i e an-
si ion s eps. A his si ua ion, o each (0 ≤ ≤m) we compu e an uppe bound
o |C (0) + C (1) + . . . +C (q)|. Then, o each i, j (0 ≤i, j ≤q, i =j) we deno e by
A (i, j) he mul ise o objec s being mo ed om egion j o egion iby applying
ules o he ype (i, u/ , j) a ime .
Le us cons uc α , 0 ≤ ≤m, an uppe bound o he numbe o objec s
which appea in he whole sys em ( aking all cells in o accoun ) a ime . Tha
is,
α ≥ |C (0) + C (1) + ...+C (q)|
The cons uc ion is made by induc ion on . Fo = 0 we conside α0=M. Le
be such ha 0 ≤ < m and o each ′(0 ≤ ′≤ ) le us assume ha we ha e
cons uc ed α ′such ha
α ′≥
q
∑
i=0
|C ′(i)|
The numbe o objec s mo ed in o cell i(1 ≤i≤q) a ins an + 1 is
A (i, 0) +
q
∑
j=1,j=i
A (i, j)
The numbe o objec s sen o he en i onmen a ins an + 1 is
q
∑
j=1
A (0, j).
No ice ha objec s coming o egion i om some o he cell jwe e al eady
p esen in he p e ious configu a ion. Besides, in o de o igge a communica ion
ule b inging objec s om he en i onmen in o egion i, a leas one objec in
egion iis equi ed, o else one symbol om Γ E in he en i onmen . Finally,
ecall ha he leng h o communica ion ules is bounded by k.
F om hese conside a ions, we deduce:
q
∑
i=1
q
∑
j=1,j=i
|A (i, j)| ≤ α and
q
∑
i=1
|A (i, 0)| ≤ α ·k
The Role o he En i onmen in Tissue P Sys ems wi h Cell Di ision 97
Besides, q
∑
j=1
|A (0, j)| ≤ α ·k
Then, we can conside α +1 =α +α ·k+α ·k=α ·(1 + 2k). Thus, o each
(0 ≤ ≤m) we define α =M·(1 + 2k) . Hence, i we applied in a consecu i e
way he maximum possible numbe o communica ion ules (wi hou applying any
di ision ules) o he sys em Π(s(u)) + cod(u), in any ins an o any compu a ion
o he sys em, M·(1 + 2k) (|u|)is an uppe bound o he numbe o objec s in he
whole sys em.
Now, le us conside he effec s o applying in a consecu i e way he maximum
possible numbe o di ision ules (wi hou applying any communica ion ules) o
he sys em Π(s(u)) + cod(u) when he ini ial configu a ion has M·(1 + 2k) (|u|)
objec s. A e ha , an uppe bound o he numbe o objec s in he whole sys em
by any compu a ion is M·(1 + 2k) (|u|)·2 (|u|)· (|u|). Hence, o each ins ance
u∈IX he numbe o objec s om Ewhich a e mo ed om he en i onmen o he
whole cells o he sys em Π(s(u))+cod(u) is, a mos , M·(1+2k) (|u|)·2 (|u|)· (|u|).
Then, we conside a polynomial unc ion p(n) such ha
p(|u|)≥log(M) + (|u|)·log(1 + 2k) + (|u|) + log( (|u|))
o each ins ance u∈IX. The polynomial unc ion p(n) ulfills he p ope y e-
qui ed a he Lemma.

6 Simula ing issue P sys ems wi h cell di ision by means o
issue P sys ems wi h cell di ision and wi hou en i onmen
The goal o his sec ion is o show ha any issue P sys em wi h cell di ision can
be simula ed by a issue P sys em wi h cell di ision and wi hou en i onmen in
an efficien way.
Fi s o all, we define he meaning o efficien simula ions in he amewo k o
ecognize issue P sys ems.
De ini ion 6.1 Le Πand Π′be ecognize issue P sys ems. We say ha Π′
simula es Πin an efficien way i he ollowing holds:
1. Π′can be cons uc ed om Πby a de e minis ic Tu ing machine wo king in
polynomial ime.
2. The e exis s an injec i e unc ion, , om he se Comp(Π)o compu a ions
o Πon o he se Comp(Π′)o compu a ions o Π′such ha :
⋆The e exis s a de e minis ic Tu ing machine ha cons uc s compu a ion
(C) om compu a ion Cin polynomial ime.
⋆A compu a ion C ∈ Comp(Π)is an accep ing compu a ion i and only i
(C)∈Comp(Π′)is an accep ing one.
104 M.J. P´e ez-Jim´enez e al.
o he objec s in he cell a e duplica ed excep he objec ha ac i a e he cell
di ision ope a ion.
In his pape , he compu a ional efficiency o issue P sys ems wi h cell di ision
and wi hou en i onmen has been s udied. We conclude ha he en i onmen o
issue P sys ems can be emo ed wi hou a loss o efficiency.
Fo u u e wo k, we plan o do u he esea ch in he s udy o issue P sys ems
wi h cell sepa a ion. Le us ecall ha , in his kind o sys ems, he applica ion o
sepa a ion ules only duplica es he cell while he objec s a e no eplica ed. They
a e simply dis ibu ed acco ding o a p efixed c i e ion.
Acknowledgemen s
The wo k was suppo ed by P ojec TIN2009-13192 o he Minis e io de Ciencia
e Inno aci´on o Spain and P ojec o Excellence wi h In es igado de Reconocida
Val´ıa, om Jun a de Andaluc´ıa, g an P08 – TIC 04200.
Re e ences
1. Gu i´e ez-Na anjo, M.A., P´e ez-Jim´enez, M.J. and Rome o-Campe o, F.J. A linea
solu ion o QSAT wi h Memb ane C ea ion. Lec u e No es in Compu e Science
3850, (2006), 241–252.
2. Pan, L. and Ishdo j, T.-O. P sys ems wi h ac i e memb anes and sepa a ion ules.
Jou nal o Uni e sal Compu e Science,10, 5, (2004), 630–649.
3. P˘aun, Gh. A acking NP-comple e p oblems. In Uncon en ional Models o Com-
pu a ion, UMC’2K (I. An oniou, C. Calude, M. J. Dinneen, eds.), Sp inge -Ve lag,
2000, 94-115.
4. P˘aun, Gh. Memb ane Compu ing. An In oduc ion. Sp inge –Ve lag, Be lin, (2002).
5. P˘aun, Gh., P´e ez-Jim´enez, M.J. and Riscos-N´u˜nez, A. Tissue P Sys em wi h cell
di ision. In. J. o Compu e s, communica ions &con ol,3, 3, (2008), 295–303.
6. P´e ez-Jim´enez, M.J., Rome o-Jim´enez, A. and Sancho-Capa ini, F. Complexi y
classes in models o cellula compu ing wi h memb anes. Na u al Compu ing,2, 3
(2003), 265–285.
7. P´e ez-Jim´enez, M.J., Rome o-Jim´enez, A. and Sancho-Capa ini, F. A polynomial
complexi y class in P sys ems using memb ane di ision. Jou nal o Au oma a, Lan-
guages and Combina o ics,11, 4, (2006), 423-434.