Monodirectional Tissue P Systems With Promoters

438 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021 Monodirectional Tissue PSystems With Promoters Bosheng Song , Xiangxiang Zeng ,Senior Member, IEEE, Min Jiang ,Senior Member, IEEE, and Mario J. Pérez-Jiménez Abstract—Tissue Psystems with promoters provide nondeterministic parallel bioinspired devices that evolve by the interchange of objects between regions, determined by the existence of some special objects called promoters.However,in cellular biology, the movement of molecules across a membrane is transported from high to low concentration. Inspired by this biological fact, in this article, an interesting type of tissue P systems, called monodirectional tissue P systems with promoters, where communication happens between two regions only in one direction, is considered. Results show that finite sets of numbers are produced by such Psystems with one cell, using any length of symport rules or with any number of cells, using a maximal length 1 of symport rules, and working in the maximally parallel mode. Monodirectional tissue Psystems are Turing universal with two cells, a maximal length 2, and at most one promoter for each symport rule, and working in the maximally parallel mode or with three cells, a maximal length 1, and at most one promoter for each symport rule, and working in the flat maximally parallel mode. We also prove that monodirectional tissue P systems with two cells, a maximal length 1, and at most one promoter for each symport rule (under certain restrictive conditions) working in the flat maximally parallel mode characterizes regular sets of natural numbers. Besides, the computational efficiency of monodirectional tissue Psystems with promoters is analyzed when cell division rules are incorporated. Different uniform solutions to the Boolean satisfiability problem (SAT problem) are provided. These results show that with the restrictive condition of “monodirectionality,” monodirectional tissue Psystems with promoters are still computationally powerful. With the powerful computational power, developing membrane algorithms for monodirectional tissue Psystems with promoters is potentially exploitable. Index Terms—Bioinspired computing, membrane computing, monodirectional tissue Psystem, NP-complete problem tissue-like network, universality. Manuscript received November 21, 2019; revised March 2, 2020 and April 20, 2020; accepted June 14, 2020. Date of publication July 10, 2020; date of current version December 22, 2020. This work was supported in part by the National Natural Science Foundation of China under Grant 61972138 and Grant 61602192, in part by the Fundamental Research Funds for the Central Universities under Grant 531118010355, in part by the Natural Science Foundation of Hunan Province of China under Grant 2020JJ4215, in part by the Research Project under Grant TIN2017-89842-P, cofinanced by Ministerio de Economía, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigación, and in part by the Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. This article was recommended by Associate Editor L. Cheng. (Corresponding author: Xiangxiang Zeng.) Bosheng Song and Xiangxiang Zeng are with the College of Information Science and Engineering, Hunan University, Changsha 410082, China (e-mail: [email protected]; [email protected]). Min Jiang is with the School of Information Science and Engineering, Xiamen University, Xiamen 361005, China (e-mail: [email protected]). Mario J. Pérez-Jiménez is with the Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, 41012 Sevilla, Spain (e-mail: [email protected]). Digital Object Identifier 10.1109/TCYB.2020.3003060 I. INTRODUCTION BIOINSPIRED computing focuses on the designs and developments of computer algorithms and models based on biological mechanisms and living phenomena, which includes quantum computing [27]; DNA computing [33], [63], [67]; membrane computing [42]; etc. In this article, we focus on the research area of membrane computing, which is an active bioinspired field initiated by P˘ aun [42], who discussed computing models motivated by the behavior and structure of cells, understanding the processes that take place in the compartments as computations. All the computing devices considered in this paradigm are called P systems [42]. Since the initial model proposes in this area, various Psystem models have been presented and investigated in the aspects of computer science [1], [22], [52]; mathematics [7], [28]; and biochemistry [15], [23]. A brief summary of membrane computing can be found in monographs [43], [45], while a review of applications of this field can be found in [14] and [21]. An essential and important component of Psystems is membrane structures that can be classified into two categories: 1) hierarchical arrangements of membranes corresponding to trees (cell-like P systems [42]) and 2) nets of membranes (neurons) corresponding to arbitrary graphs (neural-like [26], [46], [56], [58], [61], [62], [64] or tissue-like P systems [31]). The basic models studied in this work are tissue-like Psystems, which are motivated by the structure of tissue and the way of communicating substances moving from one region to another region. In a tissue Psystem, cells can communicate with other cells directly through channels and with the environment via symport/antiport rules [41]. A rule is called symport if objects go the same direction; and a rule is called antiport if some objects go the opposite directions at the same time between two regions. Inspired by various biological phenomena of cells, various tissue Psystems were constructed and investigated, most of them are turned out to be Turing complete [3], [4], [20], [40]. Besides, from mathematical, biological, and computational point of view, it is natural to incorporate mitosis (corresponding to computational rules “cell division”) [44] or membrane fission (corresponding to computational rules “cell separation”) [36] into tissue Psystems, giving them the capacity to generate an exponential space of computational units in linear time. Thanks to this mechanism, different NP-complete problems, for instance, 3-coloring [17]; vertex cover [18]; subset sum [16], [47], [55]; and satisfiability problem (SAT problem) [36], [44], [57], can be efficiently solved by means of tissue Psystems with cell separation or cell division. We 2168-2267 c 2020 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information. Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. SONG et al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 439 TABLE I RESULTS BETWEEN TISSUE PSYSTEMS WITH PROMOTERS AND MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS,WHERE prok REPRESENTS AT MOST kPROMOTERS ASSOCIATED WITH EACH RULE,sym t1REPRESENTS SYMPORT RULES OF LENGTH AT MOST t1,anti t2 REPRESENTS ANTIPORT RULES OF LENGTH AT MOST t2,∗REPRESENTS UNBOUNDED ON THE PARAMETER,AND ?REPRESENTS UNKNOWN RESULT remark that under the hypothesis P= NP,NP-complete problems cannot be solved by Psystems without cell division in polynomial time [48]. Tissue Psystems with promoters, motivated by the fact that biological reactions may occur in the presence of certain chemicals, were raised in [8] and [50]. In [8] and [50], tissue Psystems with promoters were investigated in the way of application; that is, such models were used in image processing. Moreover, tissue Psystems with promoters as generating devices of numbers were studied in [53], which was shown that such Psystems are Turing complete when different lengths of communication rules are combined (the length of a rule is defined by all numbers of objects in such a rule). Inspired by the biological fact that the movement of molecules across a membrane is transported from high to low concentration, the notion of “monodirectionality” was first proposed in cell-like Psystems (more precisely, Psystems with active membranes [29], readers can refer [6], [19], [22], and [39] for more details about Psystems with active membranes), where for two given regions, communication happens only in one direction and never in the opposite direction, that is, for two given regions, either object send-in rules or object send-out rules can be used. The motivation of this work aims at building a bridge between tissue Psystems with promoters and a variety of applications that involve information representation and information processing, thereby extending tissue Psystems with promoters to serve as a class of suitable and attractive models for these applications. Motivated by the monodirectional nature in cellular biology, a novel type of tissue P systems with promoters, called monodirectional tissue P systems with promoters, is introduced, where communication happens between two regions only in one direction, and never in the opposite direction (hence, antiport rules are forbidden to be used systems). Many applications require a monodirectional mechanism, including information acquisition device for power systems [30], [59]; some controllers for mobile robots [9], [60]; etc. In this way, the computational models are usually required to have the monodirectional nature in the sense that the transmission of information in devices can only be one way. The computational power of monodirectional tissue P systems with promoters is examined as number generators. As a result, finite sets of numbers are produced by such Psystems with one cell, using any length of symport rules or with any number of cells, using a maximal length 1 of symport rules, and working in the maximally parallel mode. Monodirectional tissue Psystems are Turing universal with two cells, a maximal length 2, and at most one promoter for each symport rule, and working in the maximally parallel mode or with three cells, a maximal length 1, and at most one promoter for each symport rule, and working in the flat maximally parallel mode (see Table I). We also prove that monodirectional tissue Psystems with two cells, a maximal length 1, and at most one promoter for each symport rule (under certain restrictive conditions) working in the flat maximally parallel mode characterizes regular sets of natural numbers. The computational efficiency of monodirectional tissue P systems with promoters is also investigated by introducing cell division rules. It is proved that the SAT problem is solved by such systems with a maximal length 1 and at most two promoters for each symport rule or with a maximal length 2 and at most one promoter for each symport rule, working in the flat maximally parallel mode (see Table I). The main contributions of this article are summarized as follows. 1) A novel type of tissue Psystems with promoters, called monodirectional tissue P systems with promoters, is developed by introducing the notion of monodirectionality into tissue Psystems with promoters. More precisely, such Psystems have a network architecture with the capability of complex topology representation. Moreover, the achieved monodirectional tissue Psystems with promoters are proved to be Turing universal. These results manifest that a Turing universal monodirectional paradigm of tissue Psystems with promoters is theoretically possible and potentially exploitable. 2) A monodirectionality control strategy is introduced into tissue Psystems with promoters to control the application of communication rules, thus making monodirectional tissue Psystems with promoters be more suitable for some applications which require a monodirectional mechanism. Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. 440 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021 3) By employing network architecture as a model structure and monodirectionality as information processing, monodirectional tissue Psystems with promoters are attractive to some real-world problems, which involve monodirectional nature and require networking model precisely. 4) Furthermore, by incorporating cell division into monodirectional tissue Psystems with promoters, the information nature in cells can be replicated, thus making monodirectional tissue Psystems with promoters be a more powerful modeling tool to develop various membrane algorithms, which makes training such systems presumable and enhances its potential for practical applications. The remainder of this article is organized as follows. Section II presents some fundamental conceptions of language and automata theory and the notion of monodirectional tissue Psystems with promoters and cell division. The computational power of the proposed Psystems is investigated in Section IV. In Section V, computational efficiency of the proposed Psystems is presented. Finally, conclusions and some future works are given in Section VI. II. PRELIMINARIES AND MODEL DESCRIPTION In this section, several fundamental conceptions from language and automata theory are recalled [51]. Also, the notion of (recognizer) monodirectional tissue Psystems with promoters and cell division is introduced. We define an alphabet (denoted by ) to be any nonempty finite set of abstract symbols. The set of strings that is concatenated by any number of symbols is denoted by ∗. +=∗\{λ}is the set that excludes the empty string (if a string does not have any symbols at all, it is called an empty string, denoted by λ). The number of symbols in a string uis the length of u, which is denoted by |u|. Let be an alphabet, and a multiset Mis two tuples (, f)such that fis a function from to N(the set of natural numbers). M() [respectively, M+()] represents the set of all multisets (respectively, nonempty multisets). If ={a1,...,ak}, then the multiset M=(, f)can be denoted by {af(a1) 1,...,af(ak) k}. If we have two multisets M1=(, f1)and M2=(, f2), then M1+M2is the union of M1and M2, which is defined by (, f1(x)+f2(x)) such that each x∈. The family of finite sets of natural numbers is denoted by NFIN, the family of regular sets of natural numbers is denoted by NREG, and we denote by NRE the family of recursively enumerable sets of natural numbers recognized by Turing machines. In order to characterize NRE, the notion of program machines is used. Readers can refer [45] for more details about program machines. It is known that program machines and Turing machines are equivalent; that is, both of them characterize NRE [32]. Next, we give the notion of monodirectional tissue P systems with promoters and cell division (the readers are suggested to refer to [53] for more information about tissue P systems with promoters). Definition 1: A monodirectional tissue Psystem with promoters and cell division of degree q≥1 has the following construction: =, E,M1,...,Mq,R,iout where 1) is a finite set of alphabet of objects; 2) Eis a set of alphabet of objects initially placed in the environment, such that E⊆; 3) Mi,1≤i≤q, are multisets of objects initially placed in qcells; 4) Ris a set of division rules and symport rules with the following restriction. a) Symport Rules: Either rules of form (pro|i,u/λ, j) orrulesofform(pro|i,λ/u,j)for two given regions exist in the system such that 0 ≤i= j≤q, pro ∈M(), and u∈M+(). b) Division Rules: [a]i→[b]i[c]isuch that i∈ {1,...,q},i= iout,a,b,c∈. 5) iout ∈{0,1,...,q}is an output region. Note that if a system does not contain cell division rules, then it is simply called a monodirectional tissue P system with promoters. Rules in monodirectional tissue Psystems with promoters (and cell division) are applied in the maximally parallel mode (a maximum degree of each rule is used in parallel) [42] or in the flat maximally parallel mode (for each computation step, a maximal applicable set of rules is selected and applied exactly once for each rule in this set) [5], [35], [54]. Aconfiguration of monodirectional tissue Psystems with promoters at an instant tis defined by a tuple (N1,...,Nq,Ne), where Ni(1 ≤i≤q) are multisets of objects over and Ne is a multiset of objects over \E. The notions of computation and halting computation are described in [42]; in particular, a configuration is a halting configuration if no rule of the system is applicable to it. Only a computation reaching a halting configuration gives a result, which is encoded by the multiset of specified objects present in the output region iout (i.e., some objects present in the output region iout may not be counted). A division rule [ a]i→[b]i[c]iis applicable if and only if object aoccurs in cell i, and cell iis not the output cell. When applying such a rule, cell iis divided into two cells with the same label: object aspecified in the cell iis replaced by object band object cin the newly generated cells, respectively; and all objects in the original cell, different from the object triggering the rule, are duplicated in the two new cells. For the application of symport rules, one is referred to [53]. Note that in monodirectional tissue Psystems with promoters and cell division, the presence of the promoter objects makes it possible to use the associated rule as many times as possible, without any restriction, that is, a promoter is valid for any number of rules (if these rules are associated with this promoter) in one step. Moreover, the promoters do not directly participate in the rules. If a symport rule does not involve promoters, then such rule is simply written by (i,u/λ, j). APsystem that computes a set of natural numbers is denoted by N(), and we denote by Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. SONG et al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 441 NOtPmon m(prok,symt,max)[respectively, NOtPmon m(prok, symt,fmax)] the family of all sets N() of natural numbers computed by systems with at most mcells, using a maximal length tand at most kpromoters for each symport rule, and working in the maximally parallel mode (respectively, in the flat maximally parallel mode). If no bound on any of parameters m,k,and tis forced, then we use symbol ∗to replace it. The definition of recognizer tissue Psystems with promoters and cell division was proposed in [53], such a model is considered to solve decision problems in a uniform way. The readers are referred to [53] for details. We denote by PMCMTPDS(prok,symt,fmax)the set of all decision problems that are solved by a family of recognizer monodirectional tissue Psystems with cell division, using a maximal length tand at most kpromoters for each symport rule in a uniform and polynomial time, and working in the flat maximally parallel mode. III. TWO EXAMPLES In order to illustrate the difference between monodirectional tissue Psystems and tissue Psystems using only symport rules (here, we consider that both of these two kinds of Psystems are worked in the maximally parallel mode), the following two examples are presented. Example 1: Let 1=(, E,M1,M2,R,1)be a monodirectional tissue Psystem (cell 1 is the output cell), where ={a},M1=M2={a}, and R={r1:(1,a/λ, 2)}. Note that rules of form (1,λ/a,2)are not allowed. At step 1, object ais sent to cell 2 from cell 1, then no rule can be used in the system, and the computation halts. So the result of computation is empty set. Example 2: Let 2=(, E,M1,M2,R,1)be a tissue Psystem using only symport rules (cell 1 is the output cell), where ={a},M1=M2={a}, and R= {r1:(1,a/λ, 2);r2:(1,λ/a,2). Now, we analyze how such Psystem works: in such Psystem, both rules r1and r2can be chosen and used. Obviously, both rules r1and r2are used in every step, and the computation never halts. So no result is obtained. IV. COMPUTATIONAL POWER OF MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS In this section, monodirectional tissue Psystems with promoters as generating devices for numbers are investigated. A. Computational Power of Monodirectional Tissue P Systems With Promoters Working the Maximally Parallel Mode In this section, monodirectional tissue Psystems with promoters as generating devices for natural numbers working in the maximally parallel mode are investigated. Theorem 1: NOtPmon 1(pro∗,sym∗,max)⊆NFIN. Proof: Keep in mind that the system contains only one cell, objects move between the environment and cell by using symport rules in one direction. Hence in such a system, communication occurs in the following two cases: 1) objects in Fig. 1. Membrane structure for the constructed monodirectional tissue P system with promoters, where circles represent cells, numbers on the side of the circles represent labels of cells, all cells are placed in the environment with label 0, and arrows indicate directions that objects are moved between two regions. the environment are moved to cell and 2) objects in the cell are moved to the environment. For case 1), symport rules are not allowed because for objects in set E(the environment), each of them has any number of copies (if symport rules are allowed in this direction, the computation will never stop); and for case 2), since there is a finite number of objects in the cell, the numbers of computation steps and reachable configurations are finite. Therefore, finite sets of numbers are generated by the system and the theorem holds. Theorem 2: NOtPmon ∗(pro∗,sym1,max)⊆NFIN. Proof: It is clear that symport rules of form (pro∗|i,λ/a,0) (i= 0,a∈E) are not allowed. So objects in set Ecannot be sent into any cells. Besides, there is a finite number of objects in the system, so the numbers of computation steps and reachable configurations are finite. Hence, finite sets of numbers are generated by the system and the theorem holds. Theorem 3: NOtPmon 2(pro1,sym2,max)=NRE. Proof: Let M=(m,H,l0,lh,I)be a program machine. The following monodirectional tissue Psystem with promoters  (see Fig. 1) is constructed to simulate M: =(, E,M1,M2,R,1) where 1) ={l,l,l,l,liv,lv,lvi,lvii|l∈H}∪{ar|1≤r≤m}; 2) E={l,lv,lvi,lvii|l∈H}∪{ar|1≤r≤m}; 3) M1={l,l,l,liv|l∈H}∪{l0},M2=∅. We design the following finite set Rof symport rules. The number of object arin cell 1 corresponds to the value of register rin M. Each ADD instruction (respectively, SUB instruction) in Mcan be simulated by six steps (respectively, eight steps) in . Initially, cell 1 contains multisets of objects {l,l,l,liv|l∈H}∪{l0}, cell 2 is empty, and the environment contains multisets of objects {l,lv,lvi,lvii|l∈H}∪{ar|1≤r≤ m}(each of these objects has an arbitrary number of copies). The program machine Mhalts corresponding to cell 1 has object lhand no rule can be applied in system . When the designed Psystem halts, the computation result for Mis the number of object a1deposited in cell 1 at this moment. 1) The following rules in Rare constructed to simulate each ADD instruction liof M: r1,i:1,lil i/λ, 2,r2,i:2,lil i/λ, 0 r3,i:1,λ/l ilv i,0,r4,i:lv i|1,l il i/λ, 2 r5,i:1,lv i/λ, 2,r6,i:2,l il i/λ, 0 r7,i:2,lv i/λ, 0,r8,i:1,λ/l iar,0 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. 442 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021 r9,i:1,λ/l ilj,0,r10,i:1,λ/l ilk,0. By applying rules r1,i,r2,i, and r3,ione by one, cell 1 will appear object lv i.Atstep4,rulesr4,iand r5,iare applied in parallel, cell 2 receives objects l i,l i,and lv i, and at the next step, the environment will receive all these objects. At step 6, cell 1 receives objects l iand arby means of applying rule r8,i; meanwhile, the system nondeterministically chooses r9,i and r10,i, and using one of these rules, the label object ljor lk is present in cell 1. Hence, during the process of simulation, the output cell increases one copy of object ar, which will simulate the next instruction ljor lk. 1) The following rules in Rare constructed to simulate each SUB instruction liof M: r11,i:1,lil i/λ, 2,r12,i:2,lil i/λ, 0 r13,i:1,λ/l ilv i,0,r14,i:lv i|1,l iar/λ, 2 r15,i:lv i|1,l iliv i/λ, 2,r16,i:1,lv i/λ, 2 r17,i:2,l iar/λ, 0,r18,i:2,l iliv i/λ, 0 r19,i:2,lv i/λ, 0,r20,i:l i|0,l ilvi i/λ, 1 r21,i:l i|1,λ/l ilvii i,0,r22,i:lvi i|1,λ/l ilj,0 r23,i:lvi i|1,λ/liv i,0,r24,i:1,lvi i/λ, 2 r25,i:lvii i|1,λ/liv ilk,0,r26,i:1,lvii i/λ, 2 r27,i:2,lvi i/λ, 0,r28,i:2,lvii i/λ, 0. The system simulates an SUB instruction lias follows. By applying rules r11,i,r12,i, and r13,ione by one, object lv iwill appear in cell 1 after three steps. At step 4, we have two cases to check whether cell 1 contains object aror not. 1) Cell 1 contains object ar. Rules r14,i,r15,i, and r16,iare applied in parallel, cell 2 receives objects l i,l i,liv i,lv i, and ar, and these objects will be sent to the environment by applying rules r17,i,r18,i,and r19,i. When the environment contains object l i, objects l iand lvi iare sent into cell 1. If cell 1 contains object lvi i, such cell will receive objects l i,liv i,and lj; meanwhile, cell 2 receives object lvi i, and the environment will receive object lvi iat the next step. Hence, during this process, the output cell decreases one copy of object ar(corresponding to subtract one from register r), which will simulate the next instruction lj. 2) Cell 1 does not contain object ar. In this case, by applying rules r15,iand r16,iin parallel, cell 2 receives objects l i,liv i,and lv i, and the environment will receive these objects at the next step by applying rules r18,iand r19,i. At this moment, if cell 1 contains object l i, such cell will receive objects l iand lvii i. When cell 1 contains object lvii i, objects liv iand lkare sent into cell 1; meanwhile, cell 2 receives object lvii i, and the environment will receive object lvii iat the next step. So when the simulation of instruction liis finished, the system will start to simulate instruction lk. So an SUB instruction can be effectively simulated for both cases. The computation halts only when cell 1 contains object lh. The number of object a1stored in cell 1 at this moment represents the computation result of M. Hence, N(M)=N(), and this concludes the proof. B. Computational Power of Monodirectional Tissue P Systems With Promoters Working in the Flat Maximally Parallel Mode In this section, the computational power of monodirectional tissue Psystems with promoters working in the flat maximally parallel mode is presented. Theorem 4: NOtPmon 2(pro1,sym1,fmax)=NREG, where two cells are labeled by 1 and 2, respectively; one cell (we assume cell 1, and cell 1 is the output cell) can receive objects from the environment and cell 2 has no communication with the environment; and objects are moved from cell 1 to cell 2. Proof: We first prove that NOtPmon 2(pro1,sym1,fmax)⊆ NREG. Let be an arbitrary monodirectional tissue Psystem with a maximal length 1 and at most 1 promoter for each symport rule (under the above restrictive conditions). The maximal number of objects increased in the system is described as follows: each object initially placed in cell 1 and each object initially placed in the environment (at some step, these objects are sent into cell 1) can be viewed as promoters, with the influence of the promoter, some copies of objects are introduced into the system; simultaneously, the promoter must be sent to cell 2, otherwise, the system never halts. Since the number of different objects initially placed in cell 1 and the number of different objects initially placed in the environment are finite, the numbers of computation steps and reachable configurations are finite. We denote these configurations by Ci,0≤i≤L, and C0is the initial configuration. We construct a regular grammar G=(N,T,C0,P), where N={Ci|0≤i≤L},Tis a set of terminal objects, and P contains the following productions. 1) Ci→aCj,forCi,Cj∈N,a∈Tsuch that there is a transition Ci⇒Cjbetween two configurations of  during which the rules introducing terminal object ainto the output cell are used. 2) Ci→Cj,forCi,Cj∈Nsuch that there is a transition Ci⇒Cjbetween two configurations of during which the output cell does not receive terminal object. 3) Ci→λ,forCi∈Nsuch that Ciis a halting configuration of . Note that if there are several copies of terminal objects introduced into the system (or output cell) at one step, then we can increase the number of configurations such that each subconfiguration introduces one copy of the terminal object. We can check that each set of natural numbers generated by system can be generated by the regular grammar G. Hence, NOtPmon 2(pro1,sym1,fmax)⊆NREG. In what follows, we prove that the converse inclusion also holds. Let G=(N,T,S,P)be an arbitrary regular grammar with the productions of the form A→aB and A→a, where A,B∈N,a∈T,S=A, and Pis the set of productions. We construct a monodirectional tissue Psystem  Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. SONG et al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 443 Fig. 2. Membrane structure of the constructed monodirectional tissue P system with promoters, where circles represent cells, numbers on the side of the circles represent labels of cells, all cells are placed in the environment with label 0, and arrows indicate directions that objects are moved between two regions. under the above restrictive conditions. Initially, Nis the alphabet of system , and object S∈N. The set of rules in  has the forms (p|1,λ/q,0)and (1,p/λ, 2). A production of the form A→aB can be simulated by using rules (A|1,λ/a,0),(A|1,λ/B,0), and (1,A/λ, 2)in one step in the mode of flat maximally parallelism. A production of the form A→acan be simulated by using rules (A|1,λ/a,0) and (1,A/λ, 2)in one step in mode of flat maximally parallelism. We can check that system  can generate the sets of natural numbers generated by grammar G. Hence, NOtPmon 2(pro1,sym1,fmax)⊇NREG. The following corollary is easy to obtain according to Theorem 4, here we omit the proof process. Corollary 1: NOtPmon 2(pro1,sym1,fmax)=NREG, where two cells are labeled by 1 and 2, respectively; both cells (we assume cell 1 is the output cell) can receive objects from the environment, and objects are moved from cell 1 to cell 2. Theorem 5: NOtPmon 3(pro1,sym1,fmax)=NRE. Proof: Let M=(m,H,l0,lh,I)be a program machine. The following monodirectional tissue Psystem with promoters  (see Fig. 2) is constructed to simulate M: =(, E,M1,M2,M3,R,1) where 1) ={l,l,l,l,liv,lv|l∈H}∪{ar|1≤r≤m}∪{d}; 2) E={l,lv|l∈H}∪{ar|1≤r≤m}; 3) M1={l,l,l|l∈H}∪{l0},M2={liv i|l∈H}∪{d}, M3=∅. We design the following finite set Rof symport rules. The number of object arin cell 1 corresponds to the value of register rin M. Each ADD instruction (respectively, SUB instruction) in Mcan be simulated by four steps (respectively, eight steps) in . Initially, cell 1 contains multisets of objects {l,l,l|l∈H}∪{l0}, cell 2 contains multisets of objects {liv i|l∈H}∪{d}, cell 3 is empty, and the environment contains multisets of objects {l,lv|l∈H}∪{ar|1≤r≤m}(each of these objects has an arbitrary number of copies). The program machine Mhalts corresponding to cell 1 has object lhand no rule can be applied in system . When the designed Psystem halts, the computation result for Mis the number of object a1deposited in cell 1 at this moment. 1) The following rules in Rare constructed to simulate each ADD instruction liof M: r1,i:(1,li/λ, 2),r2,i:li|2,liv i/λ, 0 r3,i:(2,li/λ, 0),r4,i:liv i|0,ar/λ, 1 r5,i:0,liv i/λ, 1,r6,i:1,liv i/λ, 2 r7,i:liv i|1,λ/lj,0,r8,i:liv i|1,λ/lk,0. At step 1, cell 2 receives object liby applying rule r1,i. When cell 2 contains object li, the environment will obtain object liv i; meanwhile, the environment receives object li. When the environment contains object liv i, cell 1 will receive object liv iand one copy of object ar(as flat maximal parallelism). Next, object liv iis sent back to cell 2; meanwhile, the system nondeterministically chooses r7,iand r8,i, and using one of these rules, and cell 1 will receive only one copy of label object ljor lkas using rules in the flat maximally parallel mode. Hence, during the process, the output cell increases one copy of object ar, which will simulate the next instruction lj or lk. 1) The following rules in Rare constructed to simulate each SUB instruction liof M: r9,i:(1,li/λ, 2),r10,i:li|2,liv i/λ, 0 r11,i:(2,li/λ, 0),r12,i:1,λ/liv i,0 r13,i:liv i|1,l i/λ, 2,r14,i:liv i|1,λ/lv i,0 r15,i:1,liv i/λ, 2,r16,i:l i|2,λ/ar,1 r17,i:2,l i/λ, 0,r18,i:1,lv i/λ, 2 r19 :(ar|2,d/λ, 0),r20,i:lv i|2,λ/l i,1 r21,i:lv i|2,λ/l i,1,r22,i:1,λ/l i,0 r23,i:2,lv i/λ, 0,r24,i:l i|2,ar/λ, 0 r25,i:ar|2,l i/λ, 3,r26,i:ar|2,l i/λ, 0 r27 :(1,λ/d,0),r28,i:d|2,l i/λ, 0 r29,i:d|2,l i/λ, 3,r30,i:1,λ/l i,0 r31,i:1,λ/l i,3,r32 :(1,d/λ, 2) r33,i:l i|0,lj/λ, 1,r34,i:1,λ/l i,0 r35,i:1,λ/l i,3,r36,i:l i|0,lk/λ, 1. By the application of rules r9,i,r10,i,r11,i, and r12,i,the environment will receive object liv ifrom cell 2, this object will then be sent to cell 1. When cell 1 contains object liv i, cell 2 will receive object l ifrom cell 1, and cell 1 receives only one copy of object lv i; meanwhile, cell 2 receives object liv i.Next, we have two cases to check whether cell 1 contains object ar or not. 1) Cell 1 contains object ar. Rules r16,i,r17,i, and r18,i are applied in parallel, object lv iis sent to cell 2, and the environment will receive this object later; besides, the environment and cell 1 will receive object l iin turn; and cell 2 receives one copy of object ar. When cell 2 contains object ar, the environment, cell 1, and cell 2 will receive object din turn. If cell 2 contains object lv i, cell 2 obtains objects l iand l i. Next, the environment will receive object ar; if cell 2 contains object ar, object l iis sent to cell 3, and the environment receives Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. 444 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021 object l i. At step 8, objects l iand l iare sent to cell 1 and the environment, respectively; meanwhile, when the environment contains object l i, cell 1 will receive one copy of object lj. Hence during the process, the output cell decreases one copy of object ar(corresponding to subtract one from register r), which will simulate the next instruction lj. 2) Cell 1 does not contain object ar. Only rules r17,iand r18,iare applied in parallel at step 5, cell 2 receives object lv i, and the environment will receive object lv i; in parallel, the environment receives object l i, and then cell 1 will obtain this object. If cell 2 contains object lv i, this cell will obtain objects l iand l i, and the environment and cell 3 will receive this object, respectively, (when object dstill presents in cell 2). Next, cell 1 will obtain objects l iand l i; meanwhile, when the environment contains object l i, cell 1 will receive object lk.So when the simulation is finished, the system is passed to simulate the next instruction lk. So an SUB instruction can be effectively simulated for both cases. The computation halts only when cell 1 contains object lh. The number of object a1stored in cell 1 at this moment represents the computational result of M. Hence, N(M)=N(), and this concludes the proof. V. SOLVING SAT PROBLEM BY MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS AND CELL DIVISION In this section, the SAT problem is efficiently solved by monodirectional tissue Psystems with cell division by using a maximal length 1 and at most two promoters for each symport rule or using a maximal length 2 and at most one promoter for each symport rule, working in the flat maximally parallel mode. The propositional SAT problem is defined as follows: determining whether there exists an assignment to variables that satisfies a given propositional formula or not. The SAT problem was proved to be NP-complete problem [24]. Consider a propositional formula ϕ=C1∧···∧Cmsuch that Ci=yi,1∨···∨yi,pi,pi≥1, yi,j∈{xk,¬xk|1≤k≤n}, 1≤i≤m,1≤j≤pi, and ∨and ∧represent or and and, respectively. Theorem 6: SAT∈PMCMTPDS(pro2,sym1,fmax). Proof: AuniformsolutiontothepropositionalSATproblemis givenbyafamilyofrecognizermonodirectionaltissuePsystems with promoters and cell division ={(t)|t∈N}, where each system (t)(t=n,m=((n+m)(n+m+1)/2)+n) with the input multiset cod(ϕ) will process all Boolean formulas ϕ, which have mclauses and nvariables. The recognizer monodirectional tissue Psystem with promoters and cell division is constructed as follows: (n,m)=(, E,M1,M2,M3,R,iin,iout) where 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 iout =0 are the input cell and the output region, respectively; 6) The finite set of symport rules and division rules in R is constructed as follows: r1,i:[ai]1→[ti]1[fi]1,1≤i≤n r2,i,j:tixi,j|1,λ/cj,0,1≤i≤n,1≤j≤m r3,i,j:fi¯xi,j|1,λ/cj,0,1≤i≤n,1≤j≤m r4,i:(ti|1,λ/ai+1,0),1≤i≤n r5,i:(fi|1,λ/ai+1,0),1≤i≤n r6,i:(1,ti/λ, 2),1≤i≤n r7,i:(1,fi/λ, 2),1≤i≤n r8:(an+1|1,λ/b1,0) r9:(1,an+1/λ, 2) r10,j:bjcj|1,λ/bj+1,0,1≤j≤m r11,j:1,bj/λ, 2,1≤j≤m r12 :(1,bm+1/λ, 2) r13 :(bm+1|2,yes/λ, 3) r14 :(bm+1|2,p/λ, 3) r15 :(3,yes/λ, 0) r16,i:(βi|2,λ/β i+1,0),0≤i≤2n+m+2 r17,i:(2,β i/λ, 3),0≤i≤2n+m+2 r18 :(pβ2n+m+3|2,no/λ, 3) r19 :(3,no/λ, 0). The Psystem (n,m)that solved the SAT problem consists of three stages: 1) the generation stage; 2) the checking stage; and 3) the output stage. We remark that during the computational process, a counter object βis used for counting the computation steps (by using rule r16,i); that is, for each computation step, the subscript of βis increased by 1. Generation Stage: In this stage, by applying division rules, all truth assignments for the formula ϕ(x1,...,xn)will be produced (see Fig. 3). Meanwhile, the system checks the value of all clauses by the corresponding truth assignment. This stage consists of niterations, and two steps are consumed for each iteration. So this stage takes 2nsteps. At step i=1for1≤i≤niterations, by using a rule of r1,i, two cells with the same label are obtained from dividing a cell with label 1, where objects tiand fiare distributed in each of these two cells, respectively. At step i=2for1 ≤i≤niterations, rules r2,i,j,r3,i,j,r4,i,r5,i,r6,i, and r7,iare used in parallel. When objects tiand xi,j(respectively, fiand ¯xi,j) appear in cell 1, objects ai+1and cjare introduced into that cell 1; meanwhile, by using rules r6,iand r7,i, objects tiand fiin cells 1 are sent to cell 2. The effect of rules r6,iand r7,iis to ensure that objects tiand fiappear in cell 1 only in one step, so only one copy of object ai+1and one copy of object cjare introduced into a cell due to the flat maximal parallelism. Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. SONG et al.: MONODIRECTIONAL TISSUE PSYSTEMS WITH PROMOTERS 445 Fig. 3. Membrane structure of the constructed monodirectional tissue P system with promoters and cell division at the moment when the generation stage completes, where circles represent cells, numbers on the side of the circles represent labels of cells, all cells are placed in the environment with label 0, and arrows indicate directions that objects are moved between two regions. Checking Stage: The system starts to check whether or not ϕassesses true by some truth assignments. Specifically, if all objects c1,...,cmexist in cell 1, then it means in that cell the truth assignment satisfies all clauses, so ϕassesses to TRUE; if every cell 1 does not contain all the objects c1,...,cm, then it means in each cell with label 1, the truth assignment does not satisfy at least one clause, so ϕassesses to FALSE. This stage begins at step 2n+1, which costs m+1 steps. At step 2n+1, when cell 1 contains object an+1, cell 1 will obtain object b1; meanwhile, cell 2 receives object an+1from each cell 1 by using rule r9. At step 2n+1+j(1 ≤j≤m), the system checks whether object cjexists in each cell 1. With the appearance of objects bj and cjin cell 1, this cell will receive object bj+1; meanwhile, cell 2 receives object bj. We remark that if cell 1 presents object bj+1, it means clauses C1,...,Cjare true according to the truth assignment assigned in that cell 1. Output Stage: In the output stage, the computation result is sent to the output region (i.e., the environment). If the object bm+1appears in cell 1 at step 2n+m+2, then it means the Boolean formula evaluates to TRUE. Specifically, at step 2n+m+2, by applying rule r12, cell 2 receives object bm+1. When cell 2 contains object bm+1, cell 3 receives objects p,yes, and the environment will obtain object yes at step 2n+m+4. The system halts and the computation result is affirmative. If every cell 1 does not contain object bm+1, then it means the Boolean formula evaluates to FALSE. Specifically, at step 2n+m+2, rules r16 and r17 are used in parallel, and object β2n+m+2is sent into cell 2, which will be evolved to β2n+m+3 at the next step. When cell 2 contains objects p,β 2n+m+3, cell 3 and the environment will obtain object no in turn. The system halts and the computation result is negative. In what follows, we give the resources for constructing the system: 1) the size of the alphabet: 2nm +3n+3m+8∈ O(nm); 2) the number of cells initially needed in the system: 3∈O(1); 3) the number of objects initially needed in the system: 5 ∈O(1); 4) the total number of rules in the system: 2nm +9n+4m+14 ∈O(nm); and 5) the maximum length of a rule in the system (promoters are not included): 1 ∈ O(1). Therefore, a Turing machine exists that can construct the system (n,m)in polynomial time. The designed Psystem (n,m)halts at step 2n+m+4 (the last step) for the output yes or at step 2n+m+5(the last step) for the output no. Thus, the system (n,m)is polynomially bounded concerning the numbers of clauses and variables for the formula ϕ. Therefore, the family of Psystems offers an efficient solution to the SAT problem. Theorem 7: SAT ∈PMCMTPDS(pro1,sym2,fmax). Proof: We design a family of recognizer monodirectional tissue Psystems with promoters and cell division = {(t)|t∈N}solving the SAT problem. Let (t)(t=n,m= ((n+m)(n+m+1)/2)+n) be such a tissue Psystem [associated with input cod(ϕ)], which will deal with all Boolean formulas ϕwith mclauses and nvariables. We design the recognizer monodirectional tissue Psystem with promoters and cell division as follows: (n,m)=(, E,M1,M2,M3,M4,M5,R,iin,iout) where 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 iout =0 are the input cell and the output region, respectively; 6) the finite set of symport rules and division rules in R is constructed as follows, the computation process consists of the generation stage, the checking stage, and the output stage, and an overview of the computation is presented. Generation Stage: r1:[z1]4→[z 2]4[z 2]4 r2,i:[z i]4→[z i+1]4[z i+1]4,2≤i≤n r3,i:[z i]4→[z i+1]4[z i+1]4,2≤i≤n r4:1,λ/z n+1,4 r5:z n+1|1,λ/a1,2 r6,i:[ai]1→[ti]1[fi]1,1≤i≤n r7,i,j:ti|1,xi,j/λ, 0,1≤i≤n,1≤j≤m r8,i,j:fi|1,¯xi,j/λ, 0,1≤i≤n,1≤j≤m r9,i:(ti|1,bi/λ, 0),1≤i≤n r10,i:(fi|1,bi/λ, 0),1≤i≤n r11,i,j:0,xi,jcj/λ, 2,1≤i≤n,1≤j≤m r12,i,j:0,¯xi,j¯cj/λ, 2,1≤i≤n,1≤j≤m r13,i:(0,biai+1/λ, 4),1≤i≤n r14,i,j:ti|1,λ/cj,2,1≤i≤n,1≤j≤m r15,i,j:fi|1,λ/¯cj,2,1≤i≤n,1≤j≤m r16,i:(4,ai/λ, 3),2≤i≤n+1 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply. 446 IEEE TRANSACTIONS ON CYBERNETICS, VOL. 51, NO. 1, JANUARY 2021 Fig. 4. Membrane structure of the constructed monodirectional tissue Psystem with promoters and cell division at the moment when the generation phase completes, where circles represent cells, numbers on the side of the circles represent labels of cells, all cells are placed in the environment with label 0, and arrows indicate directions that objects are moved between two regions. r17,i:(ai|3,λ/gi,2),2≤i≤n+1 r18,i:(ai|3,di−1/λ, 0),2≤i≤n+1 r19,i:(di|0,λ/ti,1),1≤i≤n r20,i:(di|0,λ/fi,1),1≤i≤n r21,i:(gi|3,ai/λ, 1),2≤i≤n+1. In the generation stage, the system works as follows. At the first nsteps, cells with label 4 are divided by using rules r1,r2,i,and r3,i, and 2ncells with label 4 are produced. Cells with label 4 play an auxiliary role, which is used for checking the clauses that are satisfied. At the next two steps, by the sequential application of rules r4and r5, object a1will be sent into cell 1 (the auxiliary object z n+1is sent to cell 1, which is used as a promoter). In the following steps, the system generates all truth assignments for the variables x1,...,xnand checks the clauses that are satisfiable. This process consists niterations, and six steps are costed for each iteration, so it takes 6nsteps for this stage. At step i=1for1≤i≤niterations, by using rule r6,i,two copies of cell 1 are produced from dividing cell 1, and each of the generated cell obtains objects tiand fi, respectively. At step i=2for1≤i≤niterations, when cell 1 contains object ti(respectively, fi), the environment receives objects xi,j and bi(respectively, ¯xi,jand bi) by applying rules r7,i,jand r9,i (respectively, r8,i,jand r10,i) in parallel. At step i=3for1≤i≤niterations, cell 2 receives xi,j,cj(respectively, ¯xi,j,¯cj) by applying rule r11,i,j(respectively, r12,i,j); meanwhile, cell 4 receives objects biand ai+1 by using rule r13,i. Note that the number of cell 4 is more than cell 1 at this moment, one copy of object biand one copy of object ai+1enter one cell with label 4 because of the flat maximal parallelism. At step i=4for1≤i≤niterations, as using rules in mode of flat maximally parallelism, rule r14,i,j(respectively, r15,i,j) is applied, cell 1 that it contains object ti(respectively, fi) receives an object cj(respectively, ¯cj). Meanwhile, cell 3 receives object aiby using rule r16,i. At step i=5for1≤i≤niterations, if object aiappears in cell 3, such cell will receive object gifrom cell 2, the environment receives object di−1from cell 3. At step i=6for1≤i≤niterations, the environment receives objects tiand fi; meanwhile, cell 1 receives object ai. In general, the generation stage costs 7n+2 steps (see Fig. 4). Checking Stage: r22 :(1,an+1c1/λ, 0) r23 :(1,an+1¯c1/λ, 0) r24,j:1,pjcj+1/λ, 0,1≤j≤m−1 r25,j:1,pj¯cj+1/λ, 0,1≤j≤m−1 r26 :an+1|1,b 1/λ, 0 r27 :an+1|1,λ/a n+1,4 r28,j:pj|1,b j+1/λ, 0,1≤j≤m−1 r29,j:h j|1,λ/p j,4,1≤j≤m−1 r30,j:1,h j/λ, 0,1≤j≤m−1 r31 :an+1|1,a n+1/λ, 0 r32,j:0,b j/λ, 4,1≤j≤m r33,j:pj|1,p j/λ, 0,1≤j≤m−1 r34,j:b j|4,λ/pjp j,0,1≤j≤m r35,j:4,b jhj/λ, 5,1≤j≤m r36 :a n+1|1,λ/p1h 1,4 Authorized licensed use limited to: Universidad de Sevilla. Downloaded on November 23,2021 at 08:50:25 UTC from IEEE Xplore. Restrictions apply.