438 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021
Monodi ec ional Tissue PSys ems Wi h P omo e s
Bosheng Song , Xiangxiang Zeng ,Senio Membe , IEEE,
Min Jiang ,Senio Membe , IEEE, and Ma io J. Pé ez-Jiménez
Abs ac —Tissue Psys ems wi h p omo e s p o ide non-
de e minis ic pa allel bioinspi ed de ices ha e ol e by he
in e change o objec s be ween egions, de e mined by he exis-
ence o some special objec s called p omo e s.Howe e ,in
cellula biology, he mo emen o molecules ac oss a memb ane
is anspo ed om high o low concen a ion. Inspi ed by his
biological ac , in his a icle, an in e es ing ype o issue P
sys ems, called monodi ec ional issue P sys ems wi h p omo e s,
whe e communica ion happens be ween wo egions only in one
di ec ion, is conside ed. Resul s show ha ini e se s o numbe s
a e p oduced by such Psys ems wi h one cell, using any leng h
o sympo ules o wi h any numbe o cells, using a maximal
leng h 1 o sympo ules, and wo king in he maximally pa al-
lel mode. Monodi ec ional issue Psys ems a e Tu ing uni e sal
wi h wo cells, a maximal leng h 2, and a mos one p omo e
o each sympo ule, and wo king in he maximally pa allel
mode o wi h h ee cells, a maximal leng h 1, and a mos one
p omo e o each sympo ule, and wo king in he la maxi-
mally pa allel mode. We also p o e ha monodi ec ional issue P
sys ems wi h wo cells, a maximal leng h 1, and a mos one p o-
mo e o each sympo ule (unde ce ain es ic i e condi ions)
wo king in he la maximally pa allel mode cha ac e izes egu-
la se s o na u al numbe s. Besides, he compu a ional e iciency
o monodi ec ional issue Psys ems wi h p omo e s is analyzed
when cell di ision ules a e inco po a ed. Di e en uni o m solu-
ions o he Boolean sa is iabili y p oblem (SAT p oblem) a e
p o ided. These esul s show ha wi h he es ic i e condi ion
o “monodi ec ionali y,” monodi ec ional issue Psys ems wi h
p omo e s a e s ill compu a ionally powe ul. Wi h he powe -
ul compu a ional powe , de eloping memb ane algo i hms o
monodi ec ional issue Psys ems wi h p omo e s is po en ially
exploi able.
Index Te ms—Bioinspi ed compu ing, memb ane compu ing,
monodi ec ional issue Psys em, NP-comple e p oblem issue-like
ne wo k, uni e sali y.
Manusc ip ecei ed No embe 21, 2019; e ised Ma ch 2, 2020 and Ap il
20, 2020; accep ed June 14, 2020. Da e o publica ion July 10, 2020; da e
o cu en e sion Decembe 22, 2020. This wo k was suppo ed in pa by
he Na ional Na u al Science Founda ion o China unde G an 61972138
and G an 61602192, in pa by he Fundamen al Resea ch Funds o he
Cen al Uni e si ies unde G an 531118010355, in pa by he Na u al
Science Founda ion o Hunan P o ince o China unde G an 2020JJ4215,
in pa by he Resea ch P ojec unde G an TIN2017-89842-P, co inanced by
Minis e io de Economía, Indus ia y Compe i i idad (MINECO) o Spain,
h ough he Agencia Es a al de In es igación, and in pa by he Fondo
Eu opeo de Desa ollo Regional (FEDER) o he Eu opean Union. This a i-
cle was ecommended by Associa e Edi o L. Cheng. (Co esponding au ho :
Xiangxiang Zeng.)
Bosheng Song and Xiangxiang Zeng a e wi h he College o In o ma ion
Science and Enginee ing, Hunan Uni e si y, Changsha 410082, China (e-mail:
[email p o ec ed]; [email p o ec ed]).
Min Jiang is wi h he School o In o ma ion Science and Enginee ing,
Xiamen Uni e si y, Xiamen 361005, China (e-mail: [email p o ec ed]).
Ma io J. Pé ez-Jiménez is wi h he Depa men o Compu e Science and
A i icial In elligence, Uni e sidad de Se illa, 41012 Se illa, Spain (e-mail:
[email p o ec ed]).
Digi al Objec Iden i ie 10.1109/TCYB.2020.3003060
I. INTRODUCTION
BIOINSPIRED compu ing ocuses on he designs and
de elopmen s o compu e algo i hms and models
based on biological mechanisms and li ing phenom-
ena, which includes quan um compu ing [27]; DNA
compu ing [33], [63], [67]; memb ane compu ing [42]; e c.
In his a icle, we ocus on he esea ch a ea o memb ane
compu ing, which is an ac i e bioinspi ed ield ini ia ed by
P˘
aun [42], who discussed compu ing models mo i a ed by he
beha io and s uc u e o cells, unde s anding he p ocesses
ha ake place in he compa men s as compu a ions. All he
compu ing de ices conside ed in his pa adigm a e called P
sys ems [42]. Since he ini ial model p oposes in his a ea, a -
ious Psys em models ha e been p esen ed and in es iga ed in
he aspec s o compu e science [1], [22], [52]; ma hema ics
[7], [28]; and biochemis y [15], [23]. A b ie summa y o
memb ane compu ing can be ound in monog aphs [43], [45],
while a e iew o applica ions o his ield can be ound in [14]
and [21].
An essen ial and impo an componen o Psys ems is mem-
b ane s uc u es ha can be classi ied in o wo ca ego ies:
1) hie a chical a angemen s o memb anes co esponding o
ees (cell-like P sys ems [42]) and 2) ne s o memb anes (neu-
ons) co esponding o a bi a y g aphs (neu al-like [26], [46],
[56], [58], [61], [62], [64] o issue-like P sys ems [31]). The
basic models s udied in his wo k a e issue-like Psys ems,
which a e mo i a ed by he s uc u e o issue and he way o
communica ing subs ances mo ing om one egion o ano he
egion. In a issue Psys em, cells can communica e wi h o he
cells di ec ly h ough channels and wi h he en i onmen ia
sympo /an ipo ules [41]. A ule is called sympo i objec s
go he same di ec ion; and a ule is called an ipo i some
objec s go he opposi e di ec ions a he same ime be ween
wo egions.
Inspi ed by a ious biological phenomena o cells, a ious
issue Psys ems we e cons uc ed and in es iga ed, mos o
hem a e u ned ou o be Tu ing comple e [3], [4], [20], [40].
Besides, om ma hema ical, biological, and compu a ional
poin o iew, i is na u al o inco po a e mi osis (co espond-
ing o compu a ional ules “cell di ision”) [44] o memb ane
ission (co esponding o compu a ional ules “cell sepa a-
ion”) [36] in o issue Psys ems, gi ing hem he capaci y o
gene a e an exponen ial space o compu a ional uni s in lin-
ea ime. Thanks o his mechanism, di e en NP-comple e
p oblems, o ins ance, 3-colo ing [17]; e ex co e [18];
subse sum [16], [47], [55]; and sa is iabili y p oblem (SAT
p oblem) [36], [44], [57], can be e icien ly sol ed by means
o issue Psys ems wi h cell sepa a ion o cell di ision. We
2168-2267 c
2020 IEEE. Pe sonal use is pe mi ed, bu epublica ion/ edis ibu ion equi es IEEE pe mission.
See h ps://www.ieee.o g/publica ions/ igh s/index.h ml o mo e in o ma ion.
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.
SONG e al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 439
TABLE I
RESULTS BETWEEN TISSUE PSYSTEMS WITH PROMOTERS AND MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS,WHERE p ok
REPRESENTS AT MOST kPROMOTERS ASSOCIATED WITH EACH RULE,sym
1REPRESENTS SYMPORT RULES OF LENGTH AT MOST 1,an i
2
REPRESENTS ANTIPORT RULES OF LENGTH AT MOST 2,∗REPRESENTS UNBOUNDED ON THE PARAMETER,AND ?REPRESENTS UNKNOWN RESULT
ema k ha unde he hypo hesis P= NP,NP-comple e p ob-
lems canno be sol ed by Psys ems wi hou cell di ision in
polynomial ime [48].
Tissue Psys ems wi h p omo e s, mo i a ed by he ac
ha biological eac ions may occu in he p esence o ce -
ain chemicals, we e aised in [8] and [50]. In [8] and [50],
issue Psys ems wi h p omo e s we e in es iga ed in he
way o applica ion; ha is, such models we e used in image
p ocessing. Mo eo e , issue Psys ems wi h p omo e s as
gene a ing de ices o numbe s we e s udied in [53], which
was shown ha such Psys ems a e Tu ing comple e when
di e en leng hs o communica ion ules a e combined ( he
leng h o a ule is de ined by all numbe s o objec s in such
a ule).
Inspi ed by he biological ac ha he mo emen o
molecules ac oss a memb ane is anspo ed om high o
low concen a ion, he no ion o “monodi ec ionali y” was i s
p oposed in cell-like Psys ems (mo e p ecisely, Psys ems
wi h ac i e memb anes [29], eade s can e e [6], [19], [22],
and [39] o mo e de ails abou Psys ems wi h ac i e mem-
b anes), whe e o wo gi en egions, communica ion happens
only in one di ec ion and ne e in he opposi e di ec ion, ha
is, o wo gi en egions, ei he objec send-in ules o objec
send-ou ules can be used.
The mo i a ion o his wo k aims a building a b idge
be ween issue Psys ems wi h p omo e s and a a ie y
o applica ions ha in ol e in o ma ion ep esen a ion and
in o ma ion p ocessing, he eby ex ending issue Psys ems
wi h p omo e s o se e as a class o sui able and a ac i e
models o hese applica ions. Mo i a ed by he monodi ec-
ional na u e in cellula biology, a no el ype o issue P
sys ems wi h p omo e s, called monodi ec ional issue P
sys ems wi h p omo e s, is in oduced, whe e communica ion
happens be ween wo egions only in one di ec ion, and ne e
in he opposi e di ec ion (hence, an ipo ules a e o bidden
o be used sys ems).
Many applica ions equi e a monodi ec ional mech-
anism, including in o ma ion acquisi ion de ice o
powe sys ems [30], [59]; some con olle s o mobile
obo s [9], [60]; e c. In his way, he compu a ional models
a e usually equi ed o ha e he monodi ec ional na u e in
he sense ha he ansmission o in o ma ion in de ices can
only be one way.
The compu a ional powe o monodi ec ional issue P
sys ems wi h p omo e s is examined as numbe gene a o s. As
a esul , ini e se s o numbe s a e p oduced by such Psys ems
wi h one cell, using any leng h o sympo ules o wi h any
numbe o cells, using a maximal leng h 1 o sympo ules,
and wo king in he maximally pa allel mode. Monodi ec ional
issue Psys ems a e Tu ing uni e sal wi h wo cells, a max-
imal leng h 2, and a mos one p omo e o each sympo
ule, and wo king in he maximally pa allel mode o wi h
h ee cells, a maximal leng h 1, and a mos one p omo e
o each sympo ule, and wo king in he la maximally pa -
allel mode (see Table I). We also p o e ha monodi ec ional
issue Psys ems wi h wo cells, a maximal leng h 1, and a
mos one p omo e o each sympo ule (unde ce ain es ic-
i e condi ions) wo king in he la maximally pa allel mode
cha ac e izes egula se s o na u al numbe s.
The compu a ional e iciency o monodi ec ional issue P
sys ems wi h p omo e s is also in es iga ed by in oducing cell
di ision ules. I is p o ed ha he SAT p oblem is sol ed
by such sys ems wi h a maximal leng h 1 and a mos wo
p omo e s o each sympo ule o wi h a maximal leng h 2
and a mos one p omo e o each sympo ule, wo king in
he la maximally pa allel mode (see Table I).
The main con ibu ions o his a icle a e summa ized as
ollows.
1) A no el ype o issue Psys ems wi h p omo e s,
called monodi ec ional issue P sys ems wi h p o-
mo e s, is de eloped by in oducing he no ion o
monodi ec ionali y in o issue Psys ems wi h p omo -
e s. Mo e p ecisely, such Psys ems ha e a ne wo k
a chi ec u e wi h he capabili y o complex opology
ep esen a ion. Mo eo e , he achie ed monodi ec ional
issue Psys ems wi h p omo e s a e p o ed o be Tu ing
uni e sal. These esul s mani es ha a Tu ing uni-
e sal monodi ec ional pa adigm o issue Psys ems
wi h p omo e s is heo e ically possible and po en ially
exploi able.
2) A monodi ec ionali y con ol s a egy is in oduced in o
issue Psys ems wi h p omo e s o con ol he applica-
ion o communica ion ules, hus making monodi ec-
ional issue Psys ems wi h p omo e s be mo e sui able
o some applica ions which equi e a monodi ec ional
mechanism.
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.
440 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021
3) By employing ne wo k a chi ec u e as a model s uc-
u e and monodi ec ionali y as in o ma ion p ocessing,
monodi ec ional issue Psys ems wi h p omo e s a e
a ac i e o some eal-wo ld p oblems, which in ol e
monodi ec ional na u e and equi e ne wo king model
p ecisely.
4) Fu he mo e, by inco po a ing cell di ision in o monodi-
ec ional issue Psys ems wi h p omo e s, he
in o ma ion na u e in cells can be eplica ed, hus mak-
ing monodi ec ional issue Psys ems wi h p omo e s be
a mo e powe ul modeling ool o de elop a ious mem-
b ane algo i hms, which makes aining such sys ems
p esumable and enhances i s po en ial o p ac ical
applica ions.
The emainde o his a icle is o ganized as ollows.
Sec ion II p esen s some undamen al concep ions o lan-
guage and au oma a heo y and he no ion o monodi ec ional
issue Psys ems wi h p omo e s and cell di ision. The com-
pu a ional powe o he p oposed Psys ems is in es iga ed
in Sec ion IV. In Sec ion V, compu a ional e iciency o he
p oposed Psys ems is p esen ed. Finally, conclusions and
some u u e wo ks a e gi en in Sec ion VI.
II. PRELIMINARIES AND MODEL DESCRIPTION
In his sec ion, se e al undamen al concep ions om lan-
guage and au oma a heo y a e ecalled [51]. Also, he no ion
o ( ecognize ) monodi ec ional issue Psys ems wi h p omo -
e s and cell di ision is in oduced.
We de ine an alphabe (deno ed by ) o be any nonemp y
ini e se o abs ac symbols. The se o s ings ha is
conca ena ed by any numbe o symbols is deno ed by ∗.
+=∗ {λ}is he se ha excludes he emp y s ing (i a
s ing does no ha e any symbols a all, i is called an emp y
s ing, deno ed by λ). The numbe o symbols in a s ing uis
he leng h o u, which is deno ed by |u|.
Le be an alphabe , and a mul ise Mis wo uples
(, )such ha is a unc ion om  o N( he se o
na u al numbe s). M() [ espec i ely, M+()] ep esen s
he se o all mul ise s ( espec i ely, nonemp y mul ise s).
I ={a1,...,ak}, hen he mul ise M=(, )can
be deno ed by {a (a1)
1,...,a (ak)
k}. I we ha e wo mul ise s
M1=(, 1)and M2=(, 2), hen M1+M2is he union
o M1and M2, which is de ined by (, 1(x)+ 2(x)) such
ha each x∈.
The amily o ini e se s o na u al numbe s is deno ed
by NFIN, he amily o egula se s o na u al numbe s is
deno ed by NREG, and we deno e by NRE he amily o
ecu si ely enume able se s o na u al numbe s ecognized by
Tu ing machines.
In o de o cha ac e ize NRE, he no ion o p og am
machines is used. Reade s can e e [45] o mo e de ails
abou p og am machines. I is known ha p og am machines
and Tu ing machines a e equi alen ; ha is, bo h o hem
cha ac e ize NRE [32].
Nex , we gi e he no ion o monodi ec ional issue P
sys ems wi h p omo e s and cell di ision ( he eade s a e sug-
ges ed o e e o [53] o mo e in o ma ion abou issue P
sys ems wi h p omo e s).
De ini ion 1: A monodi ec ional issue Psys em wi h p o-
mo e s and cell di ision o deg ee q≥1 has he ollowing
cons uc ion:
=, E,M1,...,Mq,R,iou 
whe e
1) is a ini e se o alphabe o objec s;
2) Eis a se o alphabe o objec s ini ially placed in he
en i onmen , such ha E⊆;
3) Mi,1≤i≤q, a e mul ise s o objec s ini ially placed
in qcells;
4) Ris a se o di ision ules and sympo ules wi h he
ollowing es ic ion.
a) Sympo Rules: Ei he ules o o m (p o|i,u/λ, j)
o uleso o m(p o|i,λ/u,j) o wo gi en
egions exis in he sys em such ha 0 ≤i= j≤q,
p o ∈M(), and u∈M+().
b) Di ision Rules: [a]i→[b]i[c]isuch ha i∈
{1,...,q},i= iou ,a,b,c∈.
5) iou ∈{0,1,...,q}is an ou pu egion.
No e ha i a sys em does no con ain cell di ision ules,
hen i is simply called a monodi ec ional issue P sys em wi h
p omo e s.
Rules in monodi ec ional issue Psys ems wi h p omo e s
(and cell di ision) a e applied in he maximally pa allel mode
(a maximum deg ee o each ule is used in pa allel) [42] o in
he la maximally pa allel mode ( o each compu a ion s ep, a
maximal applicable se o ules is selec ed and applied exac ly
once o each ule in his se ) [5], [35], [54].
Acon igu a ion o monodi ec ional issue Psys ems wi h
p omo e s a an ins an is de ined by a uple (N1,...,Nq,Ne),
whe e Ni(1 ≤i≤q) a e mul ise s o objec s o e and Ne
is a mul ise o objec s o e  E.
The no ions o compu a ion and hal ing compu a ion a e
desc ibed in [42]; in pa icula , a con igu a ion is a hal ing
con igu a ion i no ule o he sys em is applicable o i . Only
a compu a ion eaching a hal ing con igu a ion gi es a esul ,
which is encoded by he mul ise o speci ied objec s p esen in
he ou pu egion iou (i.e., some objec s p esen in he ou pu
egion iou may no be coun ed).
A di ision ule [ a]i→[b]i[c]iis applicable i and only
i objec aoccu s in cell i, and cell iis no he ou pu cell.
When applying such a ule, cell iis di ided in o wo cells wi h
he same label: objec aspeci ied in he cell iis eplaced by
objec band objec cin he newly gene a ed cells, espec i ely;
and all objec s in he o iginal cell, di e en om he objec
igge ing he ule, a e duplica ed in he wo new cells.
Fo he applica ion o sympo ules, one is e e ed o [53].
No e ha in monodi ec ional issue Psys ems wi h p omo e s
and cell di ision, he p esence o he p omo e objec s makes
i possible o use he associa ed ule as many imes as possi-
ble, wi hou any es ic ion, ha is, a p omo e is alid o any
numbe o ules (i hese ules a e associa ed wi h his p o-
mo e ) in one s ep. Mo eo e , he p omo e s do no di ec ly
pa icipa e in he ules. I a sympo ule does no in ol e
p omo e s, hen such ule is simply w i en by (i,u/λ, j).
APsys em  ha compu es a se o na u al
numbe s is deno ed by N(), and we deno e by
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.
SONG e al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 441
NO Pmon
m(p ok,sym ,max)[ espec i ely, NO Pmon
m(p ok,
sym , max)] he amily o all se s N() o na u al numbe s
compu ed by sys ems wi h a mos mcells, using a maximal
leng h and a mos kp omo e s o each sympo ule,
and wo king in he maximally pa allel mode ( espec i ely,
in he la maximally pa allel mode). I no bound on any o
pa ame e s m,k,and is o ced, hen we use symbol ∗ o
eplace i .
The de ini ion o ecognize issue Psys ems wi h p omo -
e s and cell di ision was p oposed in [53], such a model is
conside ed o sol e decision p oblems in a uni o m way. The
eade s a e e e ed o [53] o de ails.
We deno e by PMCMTPDS(p ok,sym , max) he se o all deci-
sion p oblems ha a e sol ed by a amily o ecognize
monodi ec ional issue Psys ems wi h cell di ision, using a
maximal leng h and a mos kp omo e s o each sympo
ule in a uni o m and polynomial ime, and wo king in he la
maximally pa allel mode.
III. TWO EXAMPLES
In o de o illus a e he di e ence be ween monodi ec ional
issue Psys ems and issue Psys ems using only sympo ules
(he e, we conside ha bo h o hese wo kinds o Psys ems
a e wo ked in he maximally pa allel mode), he ollowing wo
examples a e p esen ed.
Example 1: Le 1=(, E,M1,M2,R,1)be a monodi-
ec ional issue Psys em (cell 1 is he ou pu cell), whe e
={a},M1=M2={a}, and R={ 1:(1,a/λ, 2)}.
No e ha ules o o m (1,λ/a,2)a e no allowed. A s ep 1,
objec ais sen o cell 2 om cell 1, hen no ule can be
used in he sys em, and he compu a ion hal s. So he esul
o compu a ion is emp y se .
Example 2: Le 2=(, E,M1,M2,R,1)be a is-
sue Psys em using only sympo ules (cell 1 is he ou pu
cell), whe e ={a},M1=M2={a}, and R=
{ 1:(1,a/λ, 2); 2:(1,λ/a,2). Now, we analyze how such
Psys em wo ks: in such Psys em, bo h ules 1and 2can
be chosen and used. Ob iously, bo h ules 1and 2a e used
in e e y s ep, and he compu a ion ne e hal s. So no esul is
ob ained.
IV. COMPUTATIONAL POWER OF MONODIRECTIONAL
TISSUE PSYSTEMS WITH PROMOTERS
In his sec ion, monodi ec ional issue Psys ems wi h
p omo e s as gene a ing de ices o numbe s a e in es iga ed.
A. Compu a ional Powe o Monodi ec ional Tissue P
Sys ems Wi h P omo e s Wo king he Maximally Pa allel
Mode
In his sec ion, monodi ec ional issue Psys ems wi h p o-
mo e s as gene a ing de ices o na u al numbe s wo king in
he maximally pa allel mode a e in es iga ed.
Theo em 1: NO Pmon
1(p o∗,sym∗,max)⊆NFIN.
P oo : Keep in mind ha he sys em con ains only one
cell, objec s mo e be ween he en i onmen and cell by using
sympo ules in one di ec ion. Hence in such a sys em, com-
munica ion occu s in he ollowing wo cases: 1) objec s in
Fig. 1. Memb ane s uc u e o he cons uc ed monodi ec ional issue P
sys em wi h p omo e s, whe e ci cles ep esen cells, numbe s on he side o
he ci cles ep esen labels o cells, all cells a e placed in he en i onmen
wi h label 0, and a ows indica e di ec ions ha objec s a e mo ed be ween
wo egions.
he en i onmen a e mo ed o cell and 2) objec s in he cell
a e mo ed o he en i onmen . Fo case 1), sympo ules a e
no allowed because o objec s in se E( he en i onmen ),
each o hem has any numbe o copies (i sympo ules a e
allowed in his di ec ion, he compu a ion will ne e s op); and
o case 2), since he e is a ini e numbe o objec s in he cell,
he numbe s o compu a ion s eps and eachable con igu a ions
a e ini e. The e o e, ini e se s o numbe s a e gene a ed by
he sys em and he heo em holds.
Theo em 2: NO Pmon
∗(p o∗,sym1,max)⊆NFIN.
P oo : I is clea ha sympo ules o o m (p o∗|i,λ/a,0)
(i= 0,a∈E) a e no allowed. So objec s in se Ecanno
be sen in o any cells. Besides, he e is a ini e numbe o
objec s in he sys em, so he numbe s o compu a ion s eps
and eachable con igu a ions a e ini e. Hence, ini e se s o
numbe s a e gene a ed by he sys em and he heo em holds.
Theo em 3: NO Pmon
2(p o1,sym2,max)=NRE.
P oo : Le M=(m,H,l0,lh,I)be a p og am machine. The
ollowing monodi ec ional issue Psys em wi h p omo e s 
(see Fig. 1) is cons uc ed o simula e M:
=(, E,M1,M2,R,1)
whe e
1) ={l,l,l,l,li ,l ,l i,l ii|l∈H}∪{a |1≤ ≤m};
2) E={l,l ,l i,l ii|l∈H}∪{a |1≤ ≤m};
3) M1={l,l,l,li |l∈H}∪{l0},M2=∅.
We design he ollowing ini e se Ro sympo ules.
The numbe o objec a in cell 1 co esponds o he alue
o egis e in M. Each ADD ins uc ion ( espec i ely, SUB
ins uc ion) in Mcan be simula ed by six s eps ( espec i ely,
eigh s eps) in . Ini ially, cell 1 con ains mul ise s o objec s
{l,l,l,li |l∈H}∪{l0}, cell 2 is emp y, and he en i onmen
con ains mul ise s o objec s {l,l ,l i,l ii|l∈H}∪{a |1≤ ≤
m}(each o hese objec s has an a bi a y numbe o copies).
The p og am machine Mhal s co esponding o cell 1 has
objec lhand no ule can be applied in sys em . When he
designed Psys em hal s, he compu a ion esul o Mis
he numbe o objec a1deposi ed in cell 1 a his momen .
1) The ollowing ules in Ra e cons uc ed o simula e
each ADD ins uc ion lio M:
1,i:1,lil
i/λ, 2, 2,i:2,lil
i/λ, 0
3,i:1,λ/l
il
i,0, 4,i:l
i|1,l
il
i/λ, 2
5,i:1,l
i/λ, 2, 6,i:2,l
il
i/λ, 0
7,i:2,l
i/λ, 0, 8,i:1,λ/l
ia ,0
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.
442 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021
9,i:1,λ/l
ilj,0, 10,i:1,λ/l
ilk,0.
By applying ules 1,i, 2,i, and 3,ione by one, cell 1 will
appea objec l
i.A s ep4, ules 4,iand 5,ia e applied in
pa allel, cell 2 ecei es objec s l
i,l
i,and l
i, and a he nex
s ep, he en i onmen will ecei e all hese objec s. A s ep 6,
cell 1 ecei es objec s l
iand a by means o applying ule
8,i; meanwhile, he sys em nonde e minis ically chooses 9,i
and 10,i, and using one o hese ules, he label objec ljo lk
is p esen in cell 1. Hence, du ing he p ocess o simula ion,
he ou pu cell inc eases one copy o objec a , which will
simula e he nex ins uc ion ljo lk.
1) The ollowing ules in Ra e cons uc ed o simula e
each SUB ins uc ion lio M:
11,i:1,lil
i/λ, 2, 12,i:2,lil
i/λ, 0
13,i:1,λ/l
il
i,0, 14,i:l
i|1,l
ia /λ, 2
15,i:l
i|1,l
ili
i/λ, 2, 16,i:1,l
i/λ, 2
17,i:2,l
ia /λ, 0, 18,i:2,l
ili
i/λ, 0
19,i:2,l
i/λ, 0, 20,i:l
i|0,l
il i
i/λ, 1
21,i:l
i|1,λ/l
il ii
i,0, 22,i:l i
i|1,λ/l
ilj,0
23,i:l i
i|1,λ/li
i,0, 24,i:1,l i
i/λ, 2
25,i:l ii
i|1,λ/li
ilk,0, 26,i:1,l ii
i/λ, 2
27,i:2,l i
i/λ, 0, 28,i:2,l ii
i/λ, 0.
The sys em simula es an SUB ins uc ion lias ollows. By
applying ules 11,i, 12,i, and 13,ione by one, objec l
iwill
appea in cell 1 a e h ee s eps. A s ep 4, we ha e wo cases
o check whe he cell 1 con ains objec a o no .
1) Cell 1 con ains objec a . Rules 14,i, 15,i, and 16,ia e
applied in pa allel, cell 2 ecei es objec s l
i,l
i,li
i,l
i,
and a , and hese objec s will be sen o he en i onmen
by applying ules 17,i, 18,i,and 19,i. When he en i-
onmen con ains objec l
i, objec s l
iand l i
ia e sen
in o cell 1. I cell 1 con ains objec l i
i, such cell will
ecei e objec s l
i,li
i,and lj; meanwhile, cell 2 ecei es
objec l i
i, and he en i onmen will ecei e objec l i
ia
he nex s ep. Hence, du ing his p ocess, he ou pu cell
dec eases one copy o objec a (co esponding o sub-
ac one om egis e ), which will simula e he nex
ins uc ion lj.
2) Cell 1 does no con ain objec a . In his case, by apply-
ing ules 15,iand 16,iin pa allel, cell 2 ecei es objec s
l
i,li
i,and l
i, and he en i onmen will ecei e hese
objec s a he nex s ep by applying ules 18,iand 19,i.
A his momen , i cell 1 con ains objec l
i, such cell will
ecei e objec s l
iand l ii
i. When cell 1 con ains objec
l ii
i, objec s li
iand lka e sen in o cell 1; meanwhile, cell
2 ecei es objec l ii
i, and he en i onmen will ecei e
objec l ii
ia he nex s ep. So when he simula ion o
ins uc ion liis inished, he sys em will s a o simula e
ins uc ion lk.
So an SUB ins uc ion can be e ec i ely simula ed o bo h
cases.
The compu a ion hal s only when cell 1 con ains objec lh.
The numbe o objec a1s o ed in cell 1 a his momen ep-
esen s he compu a ion esul o M. Hence, N(M)=N(),
and his concludes he p oo .
B. Compu a ional Powe o Monodi ec ional Tissue P
Sys ems Wi h P omo e s Wo king in he Fla Maximally
Pa allel Mode
In his sec ion, he compu a ional powe o monodi ec ional
issue Psys ems wi h p omo e s wo king in he la maximally
pa allel mode is p esen ed.
Theo em 4: NO Pmon
2(p o1,sym1, max)=NREG, whe e
wo cells a e labeled by 1 and 2, espec i ely; one cell (we
assume cell 1, and cell 1 is he ou pu cell) can ecei e objec s
om he en i onmen and cell 2 has no communica ion wi h
he en i onmen ; and objec s a e mo ed om cell 1 o cell 2.
P oo : We i s p o e ha NO Pmon
2(p o1,sym1, max)⊆
NREG.
Le be an a bi a y monodi ec ional issue Psys em wi h
a maximal leng h 1 and a mos 1 p omo e o each sym-
po ule (unde he abo e es ic i e condi ions). The maximal
numbe o objec s inc eased in he sys em is desc ibed as
ollows: each objec ini ially placed in cell 1 and each objec
ini ially placed in he en i onmen (a some s ep, hese objec s
a e sen in o cell 1) can be iewed as p omo e s, wi h he in lu-
ence o he p omo e , some copies o objec s a e in oduced
in o he sys em; simul aneously, he p omo e mus be sen o
cell 2, o he wise, he sys em ne e hal s. Since he numbe o
di e en objec s ini ially placed in cell 1 and he numbe o
di e en objec s ini ially placed in he en i onmen a e ini e,
he numbe s o compu a ion s eps and eachable con igu a ions
a e ini e. We deno e hese con igu a ions by Ci,0≤i≤L,
and C0is he ini ial con igu a ion.
We cons uc a egula g amma G=(N,T,C0,P), whe e
N={Ci|0≤i≤L},Tis a se o e minal objec s, and P
con ains he ollowing p oduc ions.
1) Ci→aCj, o Ci,Cj∈N,a∈Tsuch ha he e is
a ansi ion Ci⇒Cjbe ween wo con igu a ions o 
du ing which he ules in oducing e minal objec ain o
he ou pu cell a e used.
2) Ci→Cj, o Ci,Cj∈Nsuch ha he e is a ansi ion
Ci⇒Cjbe ween wo con igu a ions o du ing which
he ou pu cell does no ecei e e minal objec .
3) Ci→λ, o Ci∈Nsuch ha Ciis a hal ing
con igu a ion o .
No e ha i he e a e se e al copies o e minal objec s
in oduced in o he sys em (o ou pu cell) a one s ep, hen
we can inc ease he numbe o con igu a ions such ha each
subcon igu a ion in oduces one copy o he e minal objec .
We can check ha each se o na u al numbe s gene a ed
by sys em can be gene a ed by he egula g amma G.
Hence, NO Pmon
2(p o1,sym1, max)⊆NREG.
In wha ollows, we p o e ha he con e se inclusion also
holds. Le G=(N,T,S,P)be an a bi a y egula g am-
ma wi h he p oduc ions o he o m A→aB and A→a,
whe e A,B∈N,a∈T,S=A, and Pis he se o p o-
duc ions. We cons uc a monodi ec ional issue Psys em 
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.

SONG e al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 443
Fig. 2. Memb ane s uc u e o he cons uc ed monodi ec ional issue P
sys em wi h p omo e s, whe e ci cles ep esen cells, numbe s on he side o
he ci cles ep esen labels o cells, all cells a e placed in he en i onmen
wi h label 0, and a ows indica e di ec ions ha objec s a e mo ed be ween
wo egions.
unde he abo e es ic i e condi ions. Ini ially, Nis he alpha-
be o sys em , and objec S∈N. The se o ules in
 has he o ms (p|1,λ/q,0)and (1,p/λ, 2). A p oduc-
ion o he o m A→aB can be simula ed by using ules
(A|1,λ/a,0),(A|1,λ/B,0), and (1,A/λ, 2)in one s ep in
he mode o la maximally pa allelism. A p oduc ion o he
o m A→acan be simula ed by using ules (A|1,λ/a,0)
and (1,A/λ, 2)in one s ep in mode o la maximally pa -
allelism. We can check ha sys em  can gene a e he
se s o na u al numbe s gene a ed by g amma G. Hence,
NO Pmon
2(p o1,sym1, max)⊇NREG.
The ollowing co olla y is easy o ob ain acco ding o
Theo em 4, he e we omi he p oo p ocess.
Co olla y 1: NO Pmon
2(p o1,sym1, max)=NREG, whe e
wo cells a e labeled by 1 and 2, espec i ely; bo h cells (we
assume cell 1 is he ou pu cell) can ecei e objec s om he
en i onmen , and objec s a e mo ed om cell 1 o cell 2.
Theo em 5: NO Pmon
3(p o1,sym1, max)=NRE.
P oo : Le M=(m,H,l0,lh,I)be a p og am machine. The
ollowing monodi ec ional issue Psys em wi h p omo e s 
(see Fig. 2) is cons uc ed o simula e M:
=(, E,M1,M2,M3,R,1)
whe e
1) ={l,l,l,l,li ,l |l∈H}∪{a |1≤ ≤m}∪{d};
2) E={l,l |l∈H}∪{a |1≤ ≤m};
3) M1={l,l,l|l∈H}∪{l0},M2={li
i|l∈H}∪{d},
M3=∅.
We design he ollowing ini e se Ro sympo ules.
The numbe o objec a in cell 1 co esponds o he alue
o egis e in M. Each ADD ins uc ion ( espec i ely, SUB
ins uc ion) in Mcan be simula ed by ou s eps ( espec i ely,
eigh s eps) in . Ini ially, cell 1 con ains mul ise s o objec s
{l,l,l|l∈H}∪{l0}, cell 2 con ains mul ise s o objec s
{li
i|l∈H}∪{d}, cell 3 is emp y, and he en i onmen con ains
mul ise s o objec s {l,l |l∈H}∪{a |1≤ ≤m}(each o
hese objec s has an a bi a y numbe o copies). The p og am
machine Mhal s co esponding o cell 1 has objec lhand no
ule can be applied in sys em . When he designed Psys em
hal s, he compu a ion esul o Mis he numbe o objec
a1deposi ed in cell 1 a his momen .
1) The ollowing ules in Ra e cons uc ed o simula e
each ADD ins uc ion lio M:
1,i:(1,li/λ, 2), 2,i:li|2,li
i/λ, 0
3,i:(2,li/λ, 0), 4,i:li
i|0,a /λ, 1
5,i:0,li
i/λ, 1, 6,i:1,li
i/λ, 2
7,i:li
i|1,λ/lj,0, 8,i:li
i|1,λ/lk,0.
A s ep 1, cell 2 ecei es objec liby applying ule 1,i.
When cell 2 con ains objec li, he en i onmen will ob ain
objec li
i; meanwhile, he en i onmen ecei es objec li. When
he en i onmen con ains objec li
i, cell 1 will ecei e objec
li
iand one copy o objec a (as la maximal pa allelism).
Nex , objec li
iis sen back o cell 2; meanwhile, he sys em
nonde e minis ically chooses 7,iand 8,i, and using one o
hese ules, and cell 1 will ecei e only one copy o label
objec ljo lkas using ules in he la maximally pa allel
mode. Hence, du ing he p ocess, he ou pu cell inc eases one
copy o objec a , which will simula e he nex ins uc ion lj
o lk.
1) The ollowing ules in Ra e cons uc ed o simula e
each SUB ins uc ion lio M:
9,i:(1,li/λ, 2), 10,i:li|2,li
i/λ, 0
11,i:(2,li/λ, 0), 12,i:1,λ/li
i,0
13,i:li
i|1,l
i/λ, 2, 14,i:li
i|1,λ/l
i,0
15,i:1,li
i/λ, 2, 16,i:l
i|2,λ/a ,1
17,i:2,l
i/λ, 0, 18,i:1,l
i/λ, 2
19 :(a |2,d/λ, 0), 20,i:l
i|2,λ/l
i,1
21,i:l
i|2,λ/l
i,1, 22,i:1,λ/l
i,0
23,i:2,l
i/λ, 0, 24,i:l
i|2,a /λ, 0
25,i:a |2,l
i/λ, 3, 26,i:a |2,l
i/λ, 0
27 :(1,λ/d,0), 28,i:d|2,l
i/λ, 0
29,i:d|2,l
i/λ, 3, 30,i:1,λ/l
i,0
31,i:1,λ/l
i,3, 32 :(1,d/λ, 2)
33,i:l
i|0,lj/λ, 1, 34,i:1,λ/l
i,0
35,i:1,λ/l
i,3, 36,i:l
i|0,lk/λ, 1.
By he applica ion o ules 9,i, 10,i, 11,i, and 12,i, he
en i onmen will ecei e objec li
i om cell 2, his objec will
hen be sen o cell 1. When cell 1 con ains objec li
i, cell 2
will ecei e objec l
i om cell 1, and cell 1 ecei es only one
copy o objec l
i; meanwhile, cell 2 ecei es objec li
i.Nex ,
we ha e wo cases o check whe he cell 1 con ains objec a
o no .
1) Cell 1 con ains objec a . Rules 16,i, 17,i, and 18,i
a e applied in pa allel, objec l
iis sen o cell 2, and
he en i onmen will ecei e his objec la e ; besides,
he en i onmen and cell 1 will ecei e objec l
iin u n;
and cell 2 ecei es one copy o objec a . When cell 2
con ains objec a , he en i onmen , cell 1, and cell 2
will ecei e objec din u n. I cell 2 con ains objec
l
i, cell 2 ob ains objec s l
iand l
i. Nex , he en i on-
men will ecei e objec a ; i cell 2 con ains objec a ,
objec l
iis sen o cell 3, and he en i onmen ecei es
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.
444 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021
objec l
i. A s ep 8, objec s l
iand l
ia e sen o cell 1
and he en i onmen , espec i ely; meanwhile, when he
en i onmen con ains objec l
i, cell 1 will ecei e one
copy o objec lj. Hence du ing he p ocess, he ou pu
cell dec eases one copy o objec a (co esponding o
sub ac one om egis e ), which will simula e he
nex ins uc ion lj.
2) Cell 1 does no con ain objec a . Only ules 17,iand
18,ia e applied in pa allel a s ep 5, cell 2 ecei es
objec l
i, and he en i onmen will ecei e objec l
i;
in pa allel, he en i onmen ecei es objec l
i, and hen
cell 1 will ob ain his objec . I cell 2 con ains objec
l
i, his cell will ob ain objec s l
iand l
i, and he en i-
onmen and cell 3 will ecei e his objec , espec i ely,
(when objec ds ill p esen s in cell 2). Nex , cell 1 will
ob ain objec s l
iand l
i; meanwhile, when he en i on-
men con ains objec l
i, cell 1 will ecei e objec lk.So
when he simula ion is inished, he sys em is passed o
simula e he nex ins uc ion lk.
So an SUB ins uc ion can be e ec i ely simula ed o bo h
cases.
The compu a ion hal s only when cell 1 con ains objec lh.
The numbe o objec a1s o ed in cell 1 a his momen ep-
esen s he compu a ional esul o M. Hence, N(M)=N(),
and his concludes he p oo .
V. SOLVING SAT PROBLEM BY MONODIRECTIONAL
TISSUE PSYSTEMS WITH PROMOTERS AND CELL
DIVISION
In his sec ion, he SAT p oblem is e icien ly sol ed by
monodi ec ional issue Psys ems wi h cell di ision by using a
maximal leng h 1 and a mos wo p omo e s o each sympo
ule o using a maximal leng h 2 and a mos one p omo e
o each sympo ule, wo king in he la maximally pa allel
mode.
The p oposi ional SAT p oblem is de ined as ollows:
de e mining whe he he e exis s an assignmen o a iables
ha sa is ies a gi en p oposi ional o mula o no . The SAT
p oblem was p o ed o be NP-comple e p oblem [24].
Conside a p oposi ional o mula ϕ=C1∧···∧Cmsuch
ha Ci=yi,1∨···∨yi,pi,pi≥1, yi,j∈{xk,¬xk|1≤k≤n},
1≤i≤m,1≤j≤pi, and ∨and ∧ ep esen o and and,
espec i ely.
Theo em 6: SAT∈PMCMTPDS(p o2,sym1, max).
P oo : Auni o msolu ion o hep oposi ionalSATp oblemis
gi enbya amilyo ecognize monodi ec ional issuePsys ems
wi h p omo e s and cell di ision ={( )| ∈N}, whe e each
sys em ( )( =n,m=((n+m)(n+m+1)/2)+n) wi h
he inpu mul ise cod(ϕ) will p ocess all Boolean o mulas ϕ,
which ha e mclauses and n a iables.
The ecognize monodi ec ional issue Psys em wi h p o-
mo e s and cell di ision is cons uc ed as ollows:
(n,m)=(, E,M1,M2,M3,R,iin,iou )
whe e
1) =∪E∪{a1,p,yes,no};
2) ={xi,j,¯xi,j|1≤i≤n,1≤j≤m};
3) E={ai|2≤i≤n}∪{bj,cj|1≤j≤m}∪{βi|0≤i≤
2n+m+3}∪{bm+1};
4) M1={a1},M2={p,β
0,yes,no},M3=∅;
5) iin =1 and iou =0 a e he inpu cell and he ou pu
egion, espec i ely;
6) The ini e se o sympo ules and di ision ules in R
is cons uc ed as ollows:
1,i:[ai]1→[ i]1[ i]1,1≤i≤n
2,i,j: ixi,j|1,λ/cj,0,1≤i≤n,1≤j≤m
3,i,j: i¯xi,j|1,λ/cj,0,1≤i≤n,1≤j≤m
4,i:( i|1,λ/ai+1,0),1≤i≤n
5,i:( i|1,λ/ai+1,0),1≤i≤n
6,i:(1, i/λ, 2),1≤i≤n
7,i:(1, i/λ, 2),1≤i≤n
8:(an+1|1,λ/b1,0)
9:(1,an+1/λ, 2)
10,j:bjcj|1,λ/bj+1,0,1≤j≤m
11,j:1,bj/λ, 2,1≤j≤m
12 :(1,bm+1/λ, 2)
13 :(bm+1|2,yes/λ, 3)
14 :(bm+1|2,p/λ, 3)
15 :(3,yes/λ, 0)
16,i:(βi|2,λ/β
i+1,0),0≤i≤2n+m+2
17,i:(2,β
i/λ, 3),0≤i≤2n+m+2
18 :(pβ2n+m+3|2,no/λ, 3)
19 :(3,no/λ, 0).
The Psys em (n,m) ha sol ed he SAT p oblem con-
sis s o h ee s ages: 1) he gene a ion s age; 2) he checking
s age; and 3) he ou pu s age. We ema k ha du ing he com-
pu a ional p ocess, a coun e objec βis used o coun ing
he compu a ion s eps (by using ule 16,i); ha is, o each
compu a ion s ep, he subsc ip o βis inc eased by 1.
Gene a ion S age: In his s age, by applying di ision ules,
all u h assignmen s o he o mula ϕ(x1,...,xn)will be p o-
duced (see Fig. 3). Meanwhile, he sys em checks he alue o
all clauses by he co esponding u h assignmen . This s age
consis s o ni e a ions, and wo s eps a e consumed o each
i e a ion. So his s age akes 2ns eps.
A s ep i=1 o 1≤i≤ni e a ions, by using a ule o
1,i, wo cells wi h he same label a e ob ained om di iding
a cell wi h label 1, whe e objec s iand ia e dis ibu ed in
each o hese wo cells, espec i ely.
A s ep i=2 o 1 ≤i≤ni e a ions, ules
2,i,j, 3,i,j, 4,i, 5,i, 6,i, and 7,ia e used in pa allel. When
objec s iand xi,j( espec i ely, iand ¯xi,j) appea in cell 1,
objec s ai+1and cja e in oduced in o ha cell 1; meanwhile,
by using ules 6,iand 7,i, objec s iand iin cells 1 a e sen
o cell 2. The e ec o ules 6,iand 7,iis o ensu e ha
objec s iand iappea in cell 1 only in one s ep, so only one
copy o objec ai+1and one copy o objec cja e in oduced
in o a cell due o he la maximal pa allelism.
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.
SONG e al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 445
Fig. 3. Memb ane s uc u e o he cons uc ed monodi ec ional issue P
sys em wi h p omo e s and cell di ision a he momen when he gene a ion
s age comple es, whe e ci cles ep esen cells, numbe s on he side o he
ci cles ep esen labels o cells, all cells a e placed in he en i onmen wi h
label 0, and a ows indica e di ec ions ha objec s a e mo ed be ween wo
egions.
Checking S age: The sys em s a s o check whe he o no
ϕassesses ue by some u h assignmen s. Speci ically, i all
objec s c1,...,cmexis in cell 1, hen i means in ha cell he
u h assignmen sa is ies all clauses, so ϕassesses o TRUE;
i e e y cell 1 does no con ain all he objec s c1,...,cm, hen
i means in each cell wi h label 1, he u h assignmen does
no sa is y a leas one clause, so ϕassesses o FALSE.
This s age begins a s ep 2n+1, which cos s m+1 s eps.
A s ep 2n+1, when cell 1 con ains objec an+1, cell 1 will
ob ain objec b1; meanwhile, cell 2 ecei es objec an+1 om
each cell 1 by using ule 9.
A s ep 2n+1+j(1 ≤j≤m), he sys em checks whe he
objec cjexis s in each cell 1. Wi h he appea ance o objec s bj
and cjin cell 1, his cell will ecei e objec bj+1; meanwhile,
cell 2 ecei es objec bj. We ema k ha i cell 1 p esen s
objec bj+1, i means clauses C1,...,Cja e ue acco ding o
he u h assignmen assigned in ha cell 1.
Ou pu S age: In he ou pu s age, he compu a ion esul is
sen o he ou pu egion (i.e., he en i onmen ).
I he objec bm+1appea s in cell 1 a s ep 2n+m+2, hen
i means he Boolean o mula e alua es o TRUE. Speci ically,
a s ep 2n+m+2, by applying ule 12, cell 2 ecei es objec
bm+1. When cell 2 con ains objec bm+1, cell 3 ecei es objec s
p,yes, and he en i onmen will ob ain objec yes a s ep
2n+m+4. The sys em hal s and he compu a ion esul is
a i ma i e.
I e e y cell 1 does no con ain objec bm+1, hen i means
he Boolean o mula e alua es o FALSE. Speci ically, a s ep
2n+m+2, ules 16 and 17 a e used in pa allel, and objec
β2n+m+2is sen in o cell 2, which will be e ol ed o β2n+m+3
a he nex s ep. When cell 2 con ains objec s p,β
2n+m+3,
cell 3 and he en i onmen will ob ain objec no in u n. The
sys em hal s and he compu a ion esul is nega i e.
In wha ollows, we gi e he esou ces o cons uc ing he
sys em: 1) he size o he alphabe : 2nm +3n+3m+8∈
O(nm); 2) he numbe o cells ini ially needed in he sys em:
3∈O(1); 3) he numbe o objec s ini ially needed in he
sys em: 5 ∈O(1); 4) he o al numbe o ules in he sys em:
2nm +9n+4m+14 ∈O(nm); and 5) he maximum leng h
o a ule in he sys em (p omo e s a e no included): 1 ∈
O(1). The e o e, a Tu ing machine exis s ha can cons uc
he sys em (n,m)in polynomial ime.
The designed Psys em (n,m)hal s a s ep 2n+m+4
( he las s ep) o he ou pu yes o a s ep 2n+m+5( he
las s ep) o he ou pu no. Thus, he sys em (n,m)is
polynomially bounded conce ning he numbe s o clauses and
a iables o he o mula ϕ.
The e o e, he amily o Psys ems o e s an e icien
solu ion o he SAT p oblem.
Theo em 7: SAT ∈PMCMTPDS(p o1,sym2, max).
P oo : We design a amily o ecognize monodi ec ional
issue Psys ems wi h p omo e s and cell di ision =
{( )| ∈N}sol ing he SAT p oblem. Le ( )( =n,m=
((n+m)(n+m+1)/2)+n) be such a issue Psys em [asso-
cia ed wi h inpu cod(ϕ)], which will deal wi h all Boolean
o mulas ϕwi h mclauses and n a iables.
We design he ecognize monodi ec ional issue Psys em
wi h p omo e s and cell di ision as ollows:
(n,m)=(, E,M1,M2,M3,M4,M5,R,iin,iou )
whe e
1) =∪E∪{bi,di|1≤i≤n}∪{b
i,hi,h
i|1≤i≤m}∪
{gi|2≤i≤n+1}∪{a1,a
n+1,b0,d0,q,z1,yes,no};
2) ={xi,j,¯xi,j|1≤i≤n,1≤j≤m};
3) E={ai|2≤i≤n+1}∪{cj,¯cj,pj,p
j|1≤j≤m}∪
{βi|0≤i≤7n+4m+7};
4) M1={b0,b1,...,bn,b
1,...,b
m},M2={β0,a1,g2,
...,gn+1},M3={d0,d1,...,dn,q,yes,no},M4=
{z1,a
n+1,h1,...,hm,h
1,...,h
m}, and M5=∅;
5) iin =1 and iou =0 a e he inpu cell and he ou pu
egion, espec i ely;
6) he ini e se o sympo ules and di ision ules in R
is cons uc ed as ollows, he compu a ion p ocess con-
sis s o he gene a ion s age, he checking s age, and
he ou pu s age, and an o e iew o he compu a ion is
p esen ed.
Gene a ion S age:
1:[z1]4→[z
2]4[z
2]4
2,i:[z
i]4→[z
i+1]4[z
i+1]4,2≤i≤n
3,i:[z
i]4→[z
i+1]4[z
i+1]4,2≤i≤n
4:1,λ/z
n+1,4
5:z
n+1|1,λ/a1,2
6,i:[ai]1→[ i]1[ i]1,1≤i≤n
7,i,j: i|1,xi,j/λ, 0,1≤i≤n,1≤j≤m
8,i,j: i|1,¯xi,j/λ, 0,1≤i≤n,1≤j≤m
9,i:( i|1,bi/λ, 0),1≤i≤n
10,i:( i|1,bi/λ, 0),1≤i≤n
11,i,j:0,xi,jcj/λ, 2,1≤i≤n,1≤j≤m
12,i,j:0,¯xi,j¯cj/λ, 2,1≤i≤n,1≤j≤m
13,i:(0,biai+1/λ, 4),1≤i≤n
14,i,j: i|1,λ/cj,2,1≤i≤n,1≤j≤m
15,i,j: i|1,λ/¯cj,2,1≤i≤n,1≤j≤m
16,i:(4,ai/λ, 3),2≤i≤n+1
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.
446 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021
Fig. 4. Memb ane s uc u e o he cons uc ed monodi ec ional issue Psys em wi h p omo e s and cell di ision a he momen when he gene a ion phase
comple es, whe e ci cles ep esen cells, numbe s on he side o he ci cles ep esen labels o cells, all cells a e placed in he en i onmen wi h label 0, and
a ows indica e di ec ions ha objec s a e mo ed be ween wo egions.
17,i:(ai|3,λ/gi,2),2≤i≤n+1
18,i:(ai|3,di−1/λ, 0),2≤i≤n+1
19,i:(di|0,λ/ i,1),1≤i≤n
20,i:(di|0,λ/ i,1),1≤i≤n
21,i:(gi|3,ai/λ, 1),2≤i≤n+1.
In he gene a ion s age, he sys em wo ks as ollows. A
he i s ns eps, cells wi h label 4 a e di ided by using ules
1, 2,i,and 3,i, and 2ncells wi h label 4 a e p oduced. Cells
wi h label 4 play an auxilia y ole, which is used o checking
he clauses ha a e sa is ied. A he nex wo s eps, by he
sequen ial applica ion o ules 4and 5, objec a1will be
sen in o cell 1 ( he auxilia y objec z
n+1is sen o cell 1,
which is used as a p omo e ).
In he ollowing s eps, he sys em gene a es all u h assign-
men s o he a iables x1,...,xnand checks he clauses ha
a e sa is iable. This p ocess consis s ni e a ions, and six s eps
a e cos ed o each i e a ion, so i akes 6ns eps o his s age.
A s ep i=1 o 1≤i≤ni e a ions, by using ule 6,i, wo
copies o cell 1 a e p oduced om di iding cell 1, and each
o he gene a ed cell ob ains objec s iand i, espec i ely.
A s ep i=2 o 1≤i≤ni e a ions, when cell 1 con ains
objec i( espec i ely, i), he en i onmen ecei es objec s xi,j
and bi( espec i ely, ¯xi,jand bi) by applying ules 7,i,jand 9,i
( espec i ely, 8,i,jand 10,i) in pa allel.
A s ep i=3 o 1≤i≤ni e a ions, cell 2 ecei es
xi,j,cj( espec i ely, ¯xi,j,¯cj) by applying ule 11,i,j( espec-
i ely, 12,i,j); meanwhile, cell 4 ecei es objec s biand ai+1
by using ule 13,i. No e ha he numbe o cell 4 is mo e
han cell 1 a his momen , one copy o objec biand one
copy o objec ai+1en e one cell wi h label 4 because o he
la maximal pa allelism.
A s ep i=4 o 1≤i≤ni e a ions, as using ules in
mode o la maximally pa allelism, ule 14,i,j( espec i ely,
15,i,j) is applied, cell 1 ha i con ains objec i( espec i ely,
i) ecei es an objec cj( espec i ely, ¯cj). Meanwhile, cell 3
ecei es objec aiby using ule 16,i.
A s ep i=5 o 1≤i≤ni e a ions, i objec aiappea s
in cell 3, such cell will ecei e objec gi om cell 2, he
en i onmen ecei es objec di−1 om cell 3.
A s ep i=6 o 1≤i≤ni e a ions, he en i onmen
ecei es objec s iand i; meanwhile, cell 1 ecei es objec ai.
In gene al, he gene a ion s age cos s 7n+2 s eps (see
Fig. 4).
Checking S age:
22 :(1,an+1c1/λ, 0)
23 :(1,an+1¯c1/λ, 0)
24,j:1,pjcj+1/λ, 0,1≤j≤m−1
25,j:1,pj¯cj+1/λ, 0,1≤j≤m−1
26 :an+1|1,b
1/λ, 0
27 :an+1|1,λ/a
n+1,4
28,j:pj|1,b
j+1/λ, 0,1≤j≤m−1
29,j:h
j|1,λ/p
j,4,1≤j≤m−1
30,j:1,h
j/λ, 0,1≤j≤m−1
31 :an+1|1,a
n+1/λ, 0
32,j:0,b
j/λ, 4,1≤j≤m
33,j:pj|1,p
j/λ, 0,1≤j≤m−1
34,j:b
j|4,λ/pjp
j,0,1≤j≤m
35,j:4,b
jhj/λ, 5,1≤j≤m
36 :a
n+1|1,λ/p1h
1,4
Au ho ized licensed use limi ed o: Uni e sidad de Se illa. Downloaded on No embe 23,2021 a 08:50:25 UTC om IEEE Xplo e. Res ic ions apply.