Monodirectional Tissue P Systems With Promoters

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.