P Systems-Based Computing Polynomials With Integer Coefficients: Design and Formal Verification

P Systems-Based Computing Polynomials With Integer Coefficients: Design and Formal Verification Ming Zhu, Gexiang Zhang , Member, IEEE , Qiang Yang, Haina Rong, Weitao Yuan, and Mario J. Pérez-Jiménez Abstract —Automatic design of mechanical procedures solving abstract problems is a relevant scientific challenge. In particular, automatic design of membranes systems performing some prefixed tasks is an important and useful research topic in the area of Natural Computing. In this context, deterministic membrane systems were designed in order to capture the values of polynomials with natural numbers coefficients. Following that work, this paper extends the previous result to polynomials with integer numbers coefficients.Specifically,a deterministic transitionP system using priorities in the weak interpretation, associated with an arbitrary such kind polynomial, is presented. The configuration of the unique computation of the system will be encoded by means of two distinguished objects, the values of the polynomial for natural numbers. The descriptive computational resources required by the designed membrane system are also analyzed. Index Terms —Membrane computing, P systems, automatic design of membrane systems, polynomials with integer coefficients. I. INTRODUCTION MEMBRANE computing is a rapidly growingbranch of natural computing initiated in [1], which abstracts computing models from the architecture and the functioning of living cells, as well as from the organization of cells in tissues, organs (the brain included), or other higher-degree structures. In the past twenty years, several classes of computing models (called P systems) were introduced, inspired This work was supported in part by the Scientific Research Fund of Sichuan Provincial Science and Technology Department under Grants 2015JY0257 and 2017FZ0010, in part by the National Nat-ural Science Foundation of China under Grants 61672437, 61702428, and 61373047, in part by the Sichuan Science and Technology Pro-gram under Grants 2018GZ0185, 2018GZ0085, and 2017GZ0159, and in part by the Fundamental Research Funds for the Central Universities under Grant A0920502051619-36. (Corresponding author: Gexiang Zhang.) M. Zhu and Q. Yang are with the College of Control Engineering, Chengdu University of Information Technology, Chengdu 610225, China (e-mail: [email protected]; [email protected]). G. Zhang, H. Rong, and W. Yuan are with the School of Electrical Engineering, Southwest Jiaotong University, Chengdu 610031, China (e-mail: [email protected]; [email protected]; [email protected]). M. J. Pérez-Jiménez is with the Department of Computer Science and Artificial Intelligence, University of Sevilla, 41012 Sevilla, Spain (e-mail: [email protected]). Fig. 1. Schematic graph showing the toolbox of artificial neural networks. Fig. 2. Schematic graph showing the aim of automatic design of P systems. from biological facts or motivated from mathematical or computer science points of view [2], [3]. Many P system classes areabletosimulateregister machines and therefore they are computationally complete, that is, they are equivalent in power to Turing machines [4]–[9]. It is well known that some P systems are efficient, in the sense that they have the ability to solve computationally hard problems by making use of an exponential workspace created in a natural way, in polynomial time [10]–[12]. Membrane computing models have been used in various applications like in the areas of approximate optimizations, systems and synthetic biology and real-life complex problems [13]–[19]. Like the toolbox of artificial neural networks (ANN) for producing successful ANNs satisfying users’ requirements, which is shown in Fig. 1, the automatic design of P systems is to develop a methodology for generating successful P systems meeting designers’ requirements, as shown in Fig. 2. This is a very complicated and challenging task. So far, the methods reported in the literature can be classified into two groups: heuristic and reasoning techniques [20]. The first type of methods focused on the use of heuristic algorithms, such as genetic algorthms (GAs) and quantum-inspired evolutionary algorithm (QIEAs), to make a population of P systems evolve toward a successful one [15]. This kind of methods began from the selection of an appropriate subset from a redundant set of evolution rules to design a cell-like P system, where a membrane structure and initial objects were pre-defined and fixed in the process of design [15], [21]–[24]. In [21], a genetic algorithm was employed to design a P system to calculate 42. In [22], a binary encoding technique was presented to denote an evolution rule set of a P system and a QIEA was used to make a population of P systems evolve toward successful ones. This method successfully solved the design of P systems to compute 42and n2(for natural numbers n≥2). In [23], an evaluation approach considering non-determinism and halting penalty factors and a genetic algorithm with the binary encoding technique in [22] were introduced to design P systems for 42,n2and the generation of the language {a2nb3n|n>1}. In these studies mentioned above, a specific redundant evolution rule set was designed for a specific computational task. This was developed in [15], [24] by applying one pre-defined redundant evolution rule set to design multiple different P systems, each of which executes a computation task. In [24], an automatic design method of a cell-like P system framework for performing five basic arithmetic operations (addition, subtraction, multiplication, division and power) was presented. In [15], a common redundant set of evolution rules was applied to design successful P systems for fulfilling eight computational tasks, i.e., eight computing sets of natural numbers: 2(n−1),2n−1, n2,1 2[n(n−1)], n(n−1),(n−1)2+2n+2, a2nb3nand 1 2(3n−1),(n>1or2). A significant development in this topic is the work in [25] in which a cell-like halting P system for 42was designed by tuning membrane structures, initial objects and evolution rules. In that work, a genetic algorithm with a binary encoding technique was discussed to codify the three ingredients of a P system, the membrane structure, initial objects and evolution rules. Following this work, an automatic design method, Permutation Penalty Genetic Algorithm (PPGA), for a deterministic and non-halting membrane system by tuning membrane structures, initial objects and evolution rules was proposed in [26]. The main ideas of PPGA are the introduction of the permutation encoding technique for a membrane system, a penalty function evaluation approach for a candidate membrane system and a genetic algorithm for making a population of P systems evolve toward a successful one fulfilling a given computational task. A cell-like membrane system for computing the square of n2(for natural numbers n≥1) was successfully designed. In addition, the automatic design of the minimal membrane systems with respect to their membrane structures, alphabet, initial objects and evolution rules to fulfill the given task were also discussed in [26]. The second type of methods use reasoning techniques to fulfill the design of a P system. In [27], a reasoning method to design a k-degree (k ≥ 2) polynomial P system was reported by analyzing the syntax and semantics of cell-like P systems. In the study of [27], deterministic transition P systems for computing polynomials with natural number coefficients were designed. The numerical values of such polynomials, p(n), for n ∈ N, are always positive and the P systems computing p(n) handle only positive numbers through the multiplicity of objects in an usual manner. In this paper, the work in [27] is extended to consider the design of deterministic transition P systems for computing polynomials with integer coefficients, where the numerical values of p(n),forn ∈ N, may be positive or negative and, consequently, the P systems computing p(n) must process integer numbers by using natural numbers in the multiplicity of objects. This task is much more challenging. The aim of this paper is to find a “minimal” such P system computing an arbitrary polynomial with integer coefficients. Here the concept “minimal” refers to some syntactical ingredients associated with P systems: the membrane structure has only one membrane and the number of objects used is very restrictive. The rest parts of this paper are organized as follows. Section II recalls some preliminaries needed in the following sections, including the specific variant of membrane systems considered in this work. The main concept of polynomial with integer coefficients computed by a deterministic transition P system is defined in Section III. The design and formal verification of a deterministic P system associated with an arbitrary polynomial whose coefficients are integer numbers, is presented in Section III-A. The descriptive computational resources required by the designed k-degree polynomial P system is analyzed in Section IV. The comparison with metaheuristic approaches is discussed in Section V. Finally, conclusions and future work are given in Section VI. II. PRELIMINARIES In this section, some general concepts are briefly described in order to make the work self-contained. A. Alphabet and Multisets An alphabet is a non-empty set and their elements are called symbols.Astring u over is an ordered finite sequence of symbols, that is, a mapping from a natural number n∈N onto . The number nis called the length of the string u and it is denoted by |u|. The empty string (with length 0) is denoted by λ.Amultiset over an alphabet is a mapping f from onto the set of natural numbers N. For each symbol a∈, the natural number f(a)is called the multiplicity of symbol ain multiset f. We denote by M() the set of all multisets over . B. Rooted Tree An undirected graph G is an ordered pair (V,E),whereV is a set whose elements are called nodes and E={{x,y}| x,y∈V,x= y}whose elements are called edges.Apath of length k≥1 from x∈Vto y∈Vis a sequence (x0,...,xk) such that x0=xand xk=y.Ifx0=xkthen we say that the path is a cycle. An undirected graph is connected if every pair of nodes is connected by a path. An undirected graph with no cycle is said to be acyclic.Arooted tree is a connected, acyclic, undirected graph in which one of the vertices (called the root of the tree) is distinguished from the others. C. Transition P Systems The basic model of membrane systems was introduced by Gh. P˘aun in its seminal paper [1]. A transition P system of degree q≥1 is a tuple =(, μ, M1,...,Mq,(R1,ρ 1),...,(Rq,ρ q), iout), where: –is a finite alphabet. –μis a rooted tree. –M1,...,Mqare multisets over . –Ri,1≤i≤q, is a finite set of evolution rules of the following forms: (a) [u]i→v1[v2[v3]j]i;and (b) [u]i→v1[v2[v3]j]iδ,wherei,j∈{1,...,q}, i= j,u,v1,v2,v3∈M() and δis a distinguished symbol such that δ/∈. –ρi,1≤i≤q, is an strict partial order over Ri. –iout ∈{0,1,...,q}. Atransition P system =(, μ, M1,...,Mq, (R1,ρ 1),...,(Rq,ρ q), iout),ofdegreeq≥1 can be viewed as a set of qmembranes injectively labeled by 1,...,q, arranged in a hierarchical structure μgiven by a rooted tree whose root is called the skin membrane of the system, and with an environment labeled by 0 such that: (a) M1,...,Mq are multisets over the working alphabet representing the objects initially placed in the qmembranes of the system; (b) Ri,1≤i≤n, is the set of rules associated with membrane i,andρiprovides priorities between rules in Ri, in such a manner that if (r1,r2)∈ρiwe say that rule r1has a higher priority than r2and we denote it by r1>r2;and (c) iout ∈{1,...,q}represents a distinguished membrane (the output membrane). Aconfiguration at an instant tof a transition P system is described by the membrane structure at instant tand all multisets of objects over associated with all the membranes present in the system. The initial configuration of the system is (μ, M1,··· ,Mq). Given a transition P system ,wesay that configuration Ctyields configuration Ct+1in one transition step, if we can pass from Ctto Ct+1by applying the rules from R1,...,Rqsynchronously, in a non-deterministic maximally parallel manner. This means the following: the objects to evolve in a transition step and the rules by which they evolve are chosen in a non-deterministic manner, but in such a way that in each membrane we have a maximally parallel application of rules (at each transition step a multiset of rules which is maximal is applied, no further applicable rule can be added). A computation of is a (finite or infinite) sequence of configurations such that: (a) the first term of the sequence is the initial configuration of the system; (b) each non-first term of the sequence is obtained from the previous configuration by applying rules of the system in a non-deterministic maximally parallel manner; and (c) if the sequence is finite then the last term of the sequence is a configuration, where no rule of the system is applicable to it. It is worth pointing out that in this paper the priority between rules is used in the weak interpretation,thatis,ina transition step a rule is used always when objects exist, which were not used by a rule of a higher priority. In this paper we deal with deterministic transition P systems, where there is only one computation starting from an initial configuration. Besides, only rules of the type [u]i→[v]iwill be used and they are briefly denoted by u→vwhen the membrane being worked with is understood. Let us consider two auxiliary functions f+and f−from the set of integer numbers Zinto the set of natural numbers N, defined as follows: f+(x)=xif x≥0 0ifx<0f−(x)=0ifx≥0 −xif x<0 It is worth pointing out that for each integer number x ∈ Z we have f+(x) ≥ 0, f−(x) ≥ 0, f+(x) + f−(x) =|x| and f+(x) − f−(x) = x. III. DETERMINISTIC TRANSITION PSYSTEMS COMPUTING POLYNOMIALS WITH INTEGER COEFFICIENTS In this section we define the meaning of computing a polynomial p(n) whose coefficients are integer numbers, by a deterministic transition P system p(n) associated with it. The idea is the following: for each natural number t ∈ N the value p(t) will be computed/encoded by the configuration Ct+1 of the unique computation of p(n). For that, four distinguished objects (o1, o2, p1, p2) will be considered in the working alphabet of p(n), in such a manner that o1, o2 will be used to encode/represent integer numbers by means of their multiplicities, and p1, p2 will be used as their corresponding transition computing objects. Definition 1: Let p(n) be a polynomial with integer numbers coefficients. We say that p(n) is computed by a deterministic transition P system p(n)=(, μ, M1,...,Mq,(R1,ρ 1),...,(Rq,ρ q), iout) if the following holds: •The working alphabet has four distinguished objects: o1,o2(the output objects) and p1,p2(transition computing objects). •For each t∈N, at configuration Ct+1the content of the output membrane labeled by iout encodes the value p(t) through the multiplicity of objects o1and o2as follows: (a) If p(t)≥0 then the multiplicity of o1is p(t)and the multiplicity of o2is 0; and (b) if p(t)<0 then the multiplicity of o2is −p(t)and the multiplicity of o1is 0. A. Design In this section, a deterministic transition P system p(n) of degree 1 that computes, in the sense of Definition 1, the polynomial p(n)=a0+a1·n···+ak·nkof degree k≥1, with integer coefficients ai∈Z,0≤i≤k, is designed. It is easy to check that for each natural number t∈Nthe following holds: p(t+1)−p(t) =[a11 0+a22 0+···+ak−1k−1 0+akk 0]·t0 +[a22 1+···+ak−1k−1 1+akk 1]·t1 ............................................. +[ak−1k−1 k−2+akk k−2]·tk−2 +[akk k−1]·tk−1 Let us denote: a0 k=a11 0+a22 0+···+ak−1k−1 0+akk 0 a1 k=a22 1+···+ak−1k−1 1+akk 1 ....................................... ak−2 k=ak−1k−1 k−2+akk k−2 ak−1 k=akk k−1 Then, p(t+1)−p(t)=a0 k+a1 k·t+a2 k·t2+···+ak−2 k·tk−2+ ak−1 k·tk−1= k−1  i=0 ai k·ti,thatis,p(t+1)=p(t)+ k−1  i=0 ai k·ti. Definition 2: Let p(n)=a0+a1·n+ ··· + ak·nk be a polynomial of degree k≥1, with integer coefficients ai∈Z,0≤i≤k. We associate p(n)with the deterministic transition P system p(n)=(, μ, M1,(R1,ρ 1), iout)of degree 1, defined as follows: •={o1,o2,p1,p2,b1,b2,b3,···bk} •μ=[] 1 •M1=of+(a0) 1of−(a0) 2b1 •R1is the set of the following evolution rules: r1≡b1→pf+(a0 k) 1pf−(a0 k) 2b(0 0) 1b(1 0) 2b(2 0) 3···b(k−2 0) k−1b(k−1 0) k r2≡b2→pf+(a1 k) 1pf−(a1 k) 2b(1 1) 2b(2 1) 3···b(k−2 1) k−1b(k−1 1) k r3≡b3→pf+(a2 k) 1pf−(a2 k) 2b(2 2) 3···b(k−2 2) k−1b(k−1 2) k . . . −rk−1≡bk−1→pf+(ak−2 k) 1pf−(ak−2 k) 2b(k−2 k−2) k−1b(k−1 k−2) k rk≡bk→pf+(ak−1 k) 1pf−(ak−1 k) 2b(k−1 k−1) k rk+1≡p1p2→λ rk+2≡p1o2→λ rk+3≡p2o1→λ rk+4≡p1→o1 rk+5≡p2→o2 •ρ1is the set of priorities relation among rules in R1: {(rk+1,rk+2), (rk+1,rk+3), (rk+2,rk+4), (rk+2,rk+5), (rk+3,rk+4), (rk+3,rk+5)}which can be informally described as: rk+1>{rk+2,rk+3}>{rk+4,rk+5}. •iout =1. B. Formal Verification We show in this subsection that the membrane system p(n) associated with the polynomial p(n), designed in the previous section, computes the values p(t)according to Definition 1, for each t∈N. Theorem 1: Let p(n)=a0+a1·n+···+ak·nkbe a polynomial of degree k≥1 such that ai∈Z,0≤i≤k. Let p(n)be the deterministic transition P system considered in Definition 1. For each t≥0, at configuration Ct+1the content of membrane labeled by 1 is the following multiset: {of+(p(t)) 1of−(p(t)) 2pk−1 i=0f+(ai k)·ti 1pk−1 i=0f−(ai k)·ti 2 b1b(t+1) 2b(t+1)2 3··· b(t+1)k−1 k} Proof: Let us prove the result by induction on t. Let us start with the base case t=0. At the initial configuration C0, the content of membrane labeled by 1 is the multiset of+(a0) 1of−(a0) 2b1. Then, configuration C0yields configuration C1by applying rule r1once. Thus, at configuration C1the content of membrane labeled by 1 is the multiset of+(a0) 1of−(a0) 2pf+a0 k 1pf−a0 k 2b1b2b3··· bk. Because of p(0)=a0=f+(a0)−f−(a0), the result holds for t=0. By induction hypothesis, let us assume the result holds for t≥0, that is, at configuration Ct+1the content of membrane labeled by 1 is the multiset {of+(p(t)) 1of−(p(t)) 2pk−1 i=0f+(ai k)·ti 1pk−1 i=0f−(ai k)·ti 2 b1b(t+1) 2b(t+1)2 3··· b(t+1)k−1 k}. In order to obtain the content of membrane labeled by 1 at configuration Ct+2, let us analyze all the possible cases that may happen: Case 1: k−1  i=0 ai k·ti≥f−(p(t)) In this case, p(t+1)−p(t)≥f−(p(t)) and the following holds: (a) k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti≥f−(p(t)). Indeed, it is sufficient to notice that ai k=f+(ai k)−f−(ai k),for0≤ i≤k−1. (b) k−1  i=0 f+(ai k)·ti≥ k−1  i=0 f−(ai k)·ti. Indeed, (b) follows from (a) recalling that f−(p(t)) ≥0. (c) p(t+1)≥0. Indeed, if p(t)≥0thenp(t+1)≥p(t)+ f−(p(t)) ≥0, and if p(t)<0then f−(p(t)) =−p(t), so p(t+1)≥p(t)+f−(p(t)) =0. Therefore, in this case configuration Ct+1yields configuration Ct+2as follows: (1) From (b) we deduce that at configuration Ct+1in membrane labeled by 1 there are more copies of object p1 than copies of object p2,so rulerk+1≡p1p2→λwill be applied k−1  i=0 f−(ai k)·titimes, consuming all copies of p2and “remaining” k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti copies of p1without evolving. (2) From (a) we deduce that at configuration Ct+1in membrane labeled by 1 there are more copies of the “remaining” object p1than copies of object o2,sorule rk+2≡p1o2→λwill be applied f−(p(t)) times, consuming all copies of o2and “remaining” k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti−f−(p(t)) copies of p1without evolving. (3) Rule rk+4≡p1→o1will be applied α= k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti−f−(p(t)) times, consuming all copies of p1and producing α copies of o1. (4) For each j,1≤j≤k,rulerj≡bj→pf+(aj−1 k) 1 pf−(aj−1 k) 2b(j−1 j−1) j...b(k−1 j−1) kwill be applied (t+1)j−1 times. All the previous rules are applied in parallel in one transition step. Thus, in this case, at configuration Ct+2the content of membrane labeled by 1 is the multiset which contains objects o1,o2,p1,p2and bj,(1≤j≤k)with the following multiplicities: –Multiplicity of o1:f+(p(t+1)). Indeed, after execution of rules from (2), αnew copies of o1are produced. Thus, the total number of copies of o1 will be: f+(p(t)) + k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti−f−(p(t)) =p(t)+ k−1  i=0 ai k·ti=p(t+1)(c) =f+(p(t+1)). –Multiplicity of o2:0. Indeed, after execution of rules from (2), all copies of object o2are consumed and any new copies of object o2 are produced for any rule applied in this transition step. Thus, at configuration Ct+2in membrane labeled by 1 the multiplicity of o2is 0. –Multiplicity of p1: k−1  i=0 f+(ai k)·(t+1)i. Indeed, after execution of rules from (1), (2) and (3), all copies of object p1are consumed but by applying rules from (4), the total number of copies of p1produced is k  j=1 f+(aj−1 k)·(t+1)j−1= k−1  i=0 f+(ai k)·(t+1)i. –Multiplicity of p2: k−1  i=0 f−(ai k)·(t+1)i. Indeed, after execution of rules from (1), (2) and (3), all copies of object p2are consumed but by applying rules from (4), the total number of copies of p2produced is k  j=1 f−(aj−1 k)·(t+1)j−1= k−1  i=0 f−(ai k)·(t+1)i. –Multiplicity of object bj, for each j,1≤j≤k: (t+2)j−1. Indeed, from (3) the total number of copies of object bj produced is j−1  s=0j−1 s(t+1)s=[(t+1)+1]j−1=(t+2)j−1 Hence, in this case the result holds for t+1. Case 2: 0≤ k−1  i=0 ai k·ti<f−(p(t)) In this case, the following holds: (a) p(t)<0andp(t+1)<0. Indeed, on the one hand, as f−(p(t)) > 0wehave f−(p(t)) =−p(t). On the other hand, p(t+1)=p(t)+ k−1  i=0 ai k·ti=−f−(p(t)) + k−1  i=0 ai k<0. (b) 0≤ k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti<f−(p(t)). Indeed, it suffices to notice that ai k=f+(ai k)−f−(ai k),for0≤ i≤k−1. (c) p(t+1)=k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti−f−(p(t)). Indeed, as f−(p(t)) > 0wehavep(t)<0and f−(p(t)) =−p(t).So, p(t+1)=p(t)+ k−1  i=0 ai k·ti =−f−(p(t)) + k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti. Therefore, in this case configuration Ct+1yields configuration Ct+2as follows: (1) From (b) we deduce that at configuration Ct+1in membrane labeled by 1 there are more copies of object p1 than copies of object p2,sorulerk+1≡p1p2→λwill be applied k−1  i=0 f−(ai k)·titimes, consuming all copies of p2and “remaining” k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti copies of p1without evolving. (2) Configuration Ct+1in membrane labeled by 1 there are more copies of object o2than copies of object p1, then rule rk+2≡p1o2→λ will be applied k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·titimes, consuming all copies of p1and “remaining” f−(p(t))− k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ticopies of o2without evolving. (3) For each j,1≤j≤k,rulerj≡bj→pf+(aj−1 k) 1 pf−(aj−1 k) 2b(j−1 j−1) j...b(k−1 j−1) kwill be applied (t+1)j−1 times. All the previous rules are applied in parallel in one transition step. Thus, in this case, at configuration Ct+2the content of membrane labeled by 1 is the multiset which contains objects o1,o2,p1,p2and bj,(1≤j≤k)with the following multiplicities: –Multiplicity of object o1:f+(p(t+1)). Indeed, the applied rules do not affect to object o1and from (a) we deduce that f+(p(t+1)) =0=f+(p(t)). –Multiplicity of object o2:f−(p(t+1)). Indeed, after execution of the cited rules, the multiplicity of o2is f−(p(t)) −k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti (b) =−p(t+1)(c) =f−(p(t+1)). –Multiplicity of object p1: k−1  i=0 f+(ai k)·(t+1)i. Indeed, after execution of the rules from (1) and (2), the multiplicity of p1is 0, but after the application of rules from (3) its multiplicity becomes k  i=1 f+(ai−1 k)·(t+1)i−1= k−1  i=0 f+(ai k)·(t+1)i –Multiplicity of object p2: k−1  i=0 f−(ai k)·(t+1)i. Indeed, because after execution of the rules from (1) and (2), the multiplicity of p2is 0, but after the application of rules from (3) its multiplicity becomes k  i=1 f−(ai−1 k)·(t+1)i−1= k−1  i=0 f−(ai k)·(t+1)i –Multiplicity of object bj, for each j,1≤j≤k: (t+2)j−1. Indeed, from (3) the total number of copies of object bj produced is j−1  s=0j−1 s(t+1)s=[(t+1)+1]j−1=(t+2)j−1 Hence, in this case the result holds for t+1. Case 3: k−1  i=0 ai k·ti<0∧f+(p(t)) + k−1  i=0 ai k·ti≤0 In this case, the following holds: (a) k−1  i=0 f+(ai k)− k−1  i=0 f−(ai k)·ti<0. Indeed, it suffices to bear in mind that k−1  i=0 ai k·ti<0, and ai k=f+(ai k)−f−(ai k),for0≤i≤k−1. (b) f+(p(t)) ≤−k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti Indeed, it is enough to notice that f+(p(t)) ≤− k−1  i=0 ai k·ti =− k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti (c) p(t+1)≤0. Indeed, if p(t)≥0thenp(t)=f+(p(t)) ≤− k−1  i=0 ai k·ti and p(t+1)=p(t)+ k−1  i=0 ai k·ti;ifp(t)<0thenp(t+1)= p(t)+ k−1  i=0 ai k·ti<0. Therefore, in this case configuration Ct+1yields configuration Ct+2as follows: (1) From (a) we deduce that at configuration Ct+1in membrane labeled by 1 there are more copies of object p2 than copies of object p1,sorulerk+1≡p1p2→λwill be applied k−1  i=0 f+(ai k)·titimes, consuming all copies of p1and “remaining” k−1  i=0 f−(ai k)·ti− k−1  i=0 f+(ai k)·ti copies of p2without evolving. (2) From (b) we deduce that at configuration Ct+1in membrane labeled by 1 there are more copies of object p2 than copies of object o1,sorulerk+3≡p2o1→λ will be applied f+(p(t)) times, consuming all copies of o1and “remaining” −f+(p(t)) + k−1  i=0 ai k·ticopies of p2without evolve but these copies must evolve by means of rule rk+5. (3) Rule rk+5≡p2→o2will be applied −f+(p(t)) + k−1  i=0 ai k·titimes, consuming all copies of p2and producing −f+(p(t)) + k−1  i=0 ai k·tinew copies of object o2. (4) For each j,1 ≤j≤k,rulerj≡ bj→pf+(aj−1 k) 1pf−(aj−1 k) 2b(j−1 j−1) j...b(k−1 j−1) kwill be applied (t+1)j−1times. All the previous rules are applied in parallel in one transition step. Thus, in this case, at configuration Ct+2the content of membrane labeled by 1 is the multiset which contains objects o1,o2,p1,p2and bj,(1≤j≤k)with the following multiplicities: –Multiplicity of object o1:f+(p(t+1)). Indeed, from (2) all copies of object t o1are consumed, but f+(p(t+1)) (c) =0. –Multiplicity of object o2:f−(p(t+1)). Indeed, after execution of the rules, its multiplicity will be f−(p(t)) −f+(p(t)) + k−1  i=0 ai k·ti =−p(t)− k−1  i=0 ai k·ti =−p(t+1)(c) =f−(p(t+1)). –Multiplicity of object p1: k−1  i=0 f+(ai k)·(t+1)i. Indeed, after execution of the rules from (1) all copies of p1are consumed but from (4) the produced copies are the following: k  i=1 f+(ai−1 k)·(t+1)i−1= k−1  i=0 f+(ai k)·(t+1)i –Multiplicity of object p2: k−1  i=0 f−(ai k)·(t+1)i. Indeed, after execution of the rules from (1), (2) and (3), all copies of object p2are consumed but by applying rules in (4) new copies of p2are produced, in total the number of copies will be: k  i=1 f−(ai−1 k)·(t+1)i−1= k−1  i=0 f−(ai k)·(t+1)i –Multiplicity of object bj, for each j,1≤j≤k: (t+2)j−1. Indeed, from (4) the total number of copies of object bj produced is j−1  s=0j−1 s(t+1)s=[(t+1)+1]j−1=(t+2)j−1 Hence, in this case the result holds for t+1. Case 4: k−1  i=0 ai k·ti<0∧f+(p(t)) + k−1  i=0 ai k·ti>0 In this case, the following holds: (a) k−1  i=0 f+(ai k)− k−1  i=0 f−(ai k)·ti<0. Indeed, it is enough to notice that k−1  i=0 ai k·ti<0, and ai k=f+(ai k)−f−(ai k),for0≤i≤k−1. (b) f+(p(t)) > −k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti. Indeed, it suffices to bear in mind that f+(p(t)) > − k−1  i=0 ai k·ti=−k−1  i=0 f+(ai k)·ti− k−1  i=0 f−(ai k)·ti and ai k=f+(ai k)−f−(ai k),for0≤i≤k−1. (c) p(t)>0andp(t+1)>0. Indeed, from the hypothesis in this case we have f+(p(t)) > − k−1  i=0 ai k·ti>0. So, p(t)>0and f+(p(t)) =p(t). Thus, p(t+1)=p(t)+ k−1  i=0 ai k·ti=f+(p(t)) + k−1  i=0 ai k·ti>0 Therefore, in this case configuration Ct+1yields configuration Ct+2as follows: (1) From (a) we deduce that at configuration Ct+1in membrane labeled by 1 there are more copies of object p2 than copies of object p1,sorulerk+1≡p1p2→λwill be applied k−1  i=0 f+(ai k)·titimes, consuming all copies of p1and “remaining” k−1  i=0 f−(ai k)·ti− k−1  i=0 f+(ai k)·ti copies of p2without evolving. (2) From (b) we deduce that at configuration Ct+1in membrane labeled by 1 there are more copies of object o1 than copies of object p2,sorulerk+3≡p1o1→λ will be applied k−1  i=0 f−(ai k)·ti− k−1  i=0 f+(ai k)·titimes, consuming all copies of p2and “remaining” f+(p(t))− k−1  i=0 f−(ai k)·ti− k−1  i=0 f+(ai k)·ticopies of o1without evolving. (3) For each j,1 ≤j≤k,rulerj≡bj→ pf+(aj−1 k) 1pf−(aj−1 k) 2b(j−1 j−1) j...b(k−1 j−1) kwill be applied (t+ 1)j−1times. All the previous rules are applied in parallel in one transition step. Thus, in this case, at configuration Ct+2the content of membrane labeled by 1 is the multiset which contains objects o1,o2,p1,p2and bj,(1≤j≤k)with the following multiplicities: –Multiplicity of object o1:f+(p(t+1)). Indeed, from (2) we deduce that the number of copies of object o1is: f+(p(t)) −k−1  i=0 f−(ai k)·ti− k−1  i=0 f+(ai k)·ti =f+(p(t)) + k−1  i=0 ai k·ti(c) =p(t)+ k−1  i=0 ai k·ti =p(t+1)(c) =f+(p(t+1)) all copies of object t o1are consumed, but f+(p(t+1)) (c) =0. –Multiplicity of object o2:f−(p(t+1)). Indeed, object o2is not involved by the application of rules to reach configuration Ct+2from configuration Ct+1, so the multiplicity of o2is f−(p(t)) (c) =0(c) =f−(p(t+1)). –Multiplicity of object p1: k−1  i=0 f+(ai k)·(t+1)i. Indeed, from (1) all copies of object p1are consumed but from (3) the total number of produced copies is k  j=1 f+(aj−1 k)·(t+1)j−1= k−1  i=0 f+(ai k)·(t+1)i. –Multiplicity of object p2: k−1  i=0 f−(ai k)·(t+1)i. Indeed, from (1) all copies of object p2are consumed but from (3) the total number of produced copies is k  j=1 f−(aj−1 k)·(t+1)j−1= k−1  i=0 f−(ai k)·(t+1)i. –Multiplicity of object bj, for each j,1≤j≤k: (t+2)j−1. Indeed, from (3) the total number of copies of object bj produced is j−1  s=0j−1 s(t+1)s=[(t+1)+1]j−1=(t+2)j−1 Hence, in this case the result holds for t+1. Corollary 1: Let p(n)=a0+a1·n+ ··· + ak·nkbe a polynomial of degree ksuch that ai∈Z,i=0,1,...,k. Let p(n)be the deterministic transition P system considered in Definition 2. Then, polynomial p(n)is computed by the system p(n)according with Definition 1. Proof: From Theorem 1 we deduce that for each t∈N at configuration Ct+1the content of membrane labeled by 1 is the following multiset: {of+(p(t)) 1of−(p(t)) 2pk−1 i=0f+(ai k)·ti 1pk−1 i=0f−(ai k)·ti 2 b1b(t+1) 2b(t+1)2 3··· b(t+1)k−1 k} In order to know the multiplicity of objects o1and o2in membrane labeled by 1 at configuration Ct+1, two cases are distinguished: •If p(t)≥0then f+(p(t)) =p(t)and f−(p(t)) =0. So, the multiplicity of o1is f+(p(t)) =p(t)and the multiplicity of o2is f−(p(t)) =0. •If p(t)<0then f+(p(t)) =0and f−(p(t)) =−p(t). Thus, the multiplicity of o1is f+(p(t)) =0andthe multiplicity of o2is f−(p(t)) =−p(t). IV. DESCRIPTIVE COMPUTATIONAL RESOURCES In this section, the descriptive computational resources required by the deterministic transition P system p(n) considered in Definition 2 which computes polynomial p(n) with integer numbers coefficients, is depicted. •The size of the working alphabet: k+4. •The initial number of objects: 1 +|a0|. •The number of rules: k+5. •The total number of objects involved in the rules is 2k+k+9+ k−1 |ai k|. i=0 Hence, the total amount of descriptive computational resources is exponential in the size of the polynomial. V. DISCUSSIONS Until now, two kinds of methods have been reported in literature to implement automatic design of membrane systems. One is the reasoning way presented in this paper and [27], which is called REASON. The other is the metaheuristic approaches (META) already used in membrane systems design, such as genetic algorithms [21], [23], [25], in particular Permutation Penalty Genetic Algorithms (PPGAs) [26], and quantum-inspired evolutionary algorithm (QIEAs) [22], [24]. REASON and META have the following differences: •Concept: META uses a metaheuristic approach to evolve a population of candidate P systems (feasible or infeasible) toward the successful P systems, while REASON uses inductive method (from simple to complex P systems) to obtain the successful P systems. A metaheuristic approach may be a genetic algorithm, a quantum-inspired evolutionary algorithm or others. •Usage: META is quite easy to understand and master for a beginner, while REASON sounds a quite complex technique to a beginner. •Generation: META is a more general technique than REASON and therefore it is possible to use META to design different P systems. While in REASON, different P systems are designed by using different specific reasoning techniques. •Resource: In REASON, it is possible to calculate the resource required by a P system with respect to computing time and workspace. While in META, it is quite hard to summarize the resource. •Software: The evaluation of a successful P system in META is performed by using the well-known P system simulator, P-Lingua [28]. REASON does not need any software. •Extendibility: REASON can be easily extended from a specific to a general P system, e.g., from a low-degree to high-degree polynomial P system, for a kind of membrane system. This extendibility is not suitable for META. VI. CONCLUSION This paper extends the work in [27] from the automatic design of deterministic transition P systems for computing polynomials with natural number coefficients to the automatic design of such kind of membrane systems for computing polynomials with integer coefficients, by analyzing the syntactical and semantics ingredients of cell-like membrane systems. This is a significant step for the programmability of membrane systems, namely how to automatically design a P system by using programs so as to develop a useful toolbox for the community of membrane computing. As future work we plan to extend this method in order to design new variants of membrane systems with the capability of performing more complex tasks like finding the minimal membrane system, with respect to the number of used objects, for a given assignment or like practical applications such as membrane controllers for mobile robots. On the other hand, we propose: (a) to develop software platforms to simulate transition P systems using a weak interpretation of the priorities as well as FPGA (Field Programmable Gate Array) based hardware to implement them; and (b) the use membrane-inspired evolutionary algorithms [15], [29], [30] or optimization spiking neural P systems [31] to implement the automatic design of a membrane systems (including spiking neural P systems) for solving computationally hard problems. REFERENCES [1] Gh. P˘aun, “Computing with membranes,” J. Comput. Syst. Sci., vol. 61, no. 1, pp. 108–143, Aug. 2000. [2] Gh. P˘aun, G. Rozenberg, and A. Salomaa, The Oxford Handbook of Membrane Computing. New York, NY, USA: Oxford Univ. Press, 2010. [3] M. Gheorghe, Gh. P˘aun, M. J. Pérez-Jiménez, and G. Rozenberg, “Research frontiers of membrane computing: Open problems and research topics,” Int. J. Found. Comput. Sci., vol. 24, no. 5, pp. 547–624, 2013. [4] Gh. P˘aun, Y. Suzuki, and H. Tanaka, “On the power of membrane division in P systems,” Theor. Comput. Sci., vol. 324, no. 1, pp. 61–85, 2004. [5] C. Martín-Vide, Gh. P˘aun, J. Pazos, and A. Rodríguez-Patón, “Tissue Psystems,”Theor. Comput. Sci., vol. 296, no. 2, pp. 295–326, 2003. [6] M. Ionescu, Gh. P˘aun, and T. Yokomori, “Spiking neural P systems,” Fundam. Inf., vol. 71, no. 2, pp. 279–308, 2006. [7] L. Pan and X. Zeng, “Small universal spiking neural P systems working in exhaustive mode,” IEEE Trans. Nanobiosci., vol. 10, no. 2, pp. 99–105, Jun. 2011. [8] L. Pan, J. Wang, and H. J. Hoogeboom, “Spiking neural P systems with astrocytes,” Neural Comput., vol. 24, no. 3, pp. 805–825, 2012. [9] L. Pan, Gh. P˘aun, G. Zhang, and F. Neri, “Spiking neural P systems with communication on request,” Int. J. Neural Syst., vol. 27, no. 8, 2017, Art. no. 1750042. [10] A. Alhazov, C. Martín-Vide, and L. Pan, “Solving a PSPACE- complete problem by recognizing P systems with restricted active membranes,” Fundamenta Informaticae, vol. 58, no. 2, pp. 66–77, 2003. [11] L. Pan and C. Martin-Vide, “Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes,” J. Parallel Distrib. Comput., vol. 65, no. 12, pp. 1578–1584, 2005. [12] B. Song, T. Song, and L. Pan, “Time-free solution to sat problem by P systems with active membranes and standard cell division rules,” Natural Comput., vol. 14, no. 4, pp. 673–681, 2015. [13] G. Ciobanu, M. J. Pérez-Jiménez, and Gh. P˘aun, Eds., Applications of Membrane Computing (Natural Computing Series). Berlin, Germany: Springer, 2006. [14] P. Frisco, M. Gheorghe, M. J. Pérez-Jiménez, Eds., Applications of Membrane Computing in Systems and Synthetic Biology (Emergence, Complexity and Computation). Berlin, Germany: Springer, 2014. [15] G. Zhang, M. Gheorghe, L. Pan, and M. J. Pérez-Jiménez, “Evolutionary membrane computing: A comprehensive survey and new results,” Inf. Sci., vol. 279, pp. 528–551, Sep. 2014. [16] G. Zhang, M. J. Pérez-Jiménez, and M. Gheorghe, Real-life Applications with Membrane Computing (Emergence, Complexity and Computation). Berlin, Germany: Springer, 2017. [17] H. Peng, J. Wang, M. J. Pérez-Jiménez, H. Wang, J. Shao, and T. Wang, “Fuzzy reasoning spiking neural P system for fault diagnosis,” Inf. Sci., vol. 235, pp. 106–116, Jun. 2013. [18] C. Buiu, C. Vasile, and O. Arsene, “Development of membrane controllers for mobile robots,” Inf. Sci., vol. 187, no. 1, pp. 33–51, 2012. [19] X. Wang et al., “Design and implementation of membrane controllers for trajectory tracking of nonholonomic wheeled mobile robots,” Integr. Comput.-Aided Eng., vol. 23, no. 1, pp. 15–30, 2016. [20] G. Zhang, J. Cheng, T. Wang, X. Wang, and J. Zhu, Eds., Membrane Computing: Theory and Applications. Beijing, China: Science Press, 2015. [21] G. Escuela and M. Á. G. Naranjo, “An application of genetic algorithms to membrane computing,” in Proc. 8th Brainstorming Week Membrane Comput., 2010, pp. 101–108. [22] X. Huang, G. Zhang, H. Rong, and F. Ipate, “Evolutionary design of a simple membrane system,” in Membrane Computing (Lecture Notes in Computer Science), vol. 7184, M. Gheorghe, Gh. P˘aun, G. Rozenberg, A. Salomaa, and S. Verlan, Eds. Berlin, Germany: Springer, 2012, pp. 203–214. [23] C. Tudose, R. Lefticaru, and F. Ipate, “Using genetic algorithms and model checking for P systems automatic design,” in Nature Inspired Cooperative Strategies for Optimization (Studies in Computational Intelligence), vol. 387, D. A. Pelta, N. Krasnogor, D. Dumitrescu, C. Chira, and R. Lung, Eds. Berlin, Germany: Springer, 2011, pp. 285–302. [24] Y. Chen, G. Zhang, T. Wang, and X. Huang, “Automatic design of a P system for basic arithmetic operations,” Chin.J.Electron., vol. 23, no. 2, pp. 302–304, 2014. [25] Z. Ou, G. Zhang, T. Wang, and X. Huang, “Automatic design of celllike P systems through tuning membrane structures, initial objects and evolution rules,” Int. J. Unconventional Comput., vol. 9, nos. 5–6, pp. 425–443, 2013. [26] G. Zhang, H. Rong, Z. Ou, M. J. Pérez-Jiménez, and M. Gheorghe, “Automatic design of deterministic and non-halting membrane systems by tuning syntactical ingredients,” IEEE Trans. Nanobiosci., vol. 13, no. 3, pp. 363–371, Sep. 2014. [27] W. Yuan, G. Zhang, M. J. Pérez-Jiménez, T. Wang, and X. Huang, “P systems based computing polynomials: Design and formal verification,” Natural Comput., vol. 15, no. 4, pp. 591–596, 2016. [28] M. García-Quismondo, R. Gutiérrez-Escudero, I. Pérez-Hurtado, M. J. Pérez-Jiménez, and A. Riscos-Núñez, “An overview of P-lingua 2.0,” in Workshop Membrane Computing (Lecture Notes in Computer Science), vol. 5957, Gh. P˘aun, M. J. Pérez-Jiménez, A. Riscos-Núñez, G. Rozenberg, and A. Salomaa, Eds. Berlin, Germany: Springer, 2010, pp. 264–288. [29] G. Zhang, J. Cheng, M. Gheorghe, and Q. Meng, “A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems,” Appl. Soft Comput., vol. 13, no. 3, pp. 1528–1542, 2013. [30] J. Xiao, Y. Huang, Z. Cheng, J. He, and Y. Niu, “A hybrid membrane evolutionary algorithm for solving constrained optimization problems,” Optik, vol. 125, no. 2, pp. 897–902, 2014. [31] G. Zhang, H. Rong, F. Neri, and M. J. Pérez-Jiménez, “An optimization spiking neural P system for approximately solving combinatorial optimization problems,” Int. J. Neural Syst., vol. 24, no. 5, pp. 1–16, 2014.