P Systems based Computing Polynomials: Design and Formal Verification

P Systems based Computing Polynomials: Design and Formal Verification Weitao Yuan1, Gexiang Zhang1⋆, Mario J. P´erez-Jim´enez2, Tao Wang1, and Zhiwei Huang1 1School of Electrical Engineering, Southwest Jiaotong University, Chengdu, 610031, P.R. China email: [email protected], [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla, Sevilla, 41012, Spain email: marp[email protected] Abstract. Automatic design of P systems is an attractive research topic in the community of membrane computing. Differing from the previous work that used evolutionary algorithms to fulfill the task, this paper presents the design of a simple (deterministic transition) P system (without input membrane) of degree 1, capturing the value of the korder (k≥2) polynomial by using a reasoning method. Specifically, the values of polynomial p(n) corresponding to a natural number tis equal to the multiplicity of a distinguished object of the system (the output object) in the configuration at instant t. We also discuss the descriptive computational resources required by the designed k-order polynomial P system. Keywords: Membrane computing, P system, automatic design, polynomial. 1 Introduction Since the area of membrane computing was initiated in 1998 [1], the rapidly theoretical development with respect to computing models and their computing power and computational efficiency [2] and various real-world applications [3, 4] have been reported. A P system for performing a specific task, especially for solving an NP-hard, NP-complete or PSPACE-complete problem or for controlling robots, is carefully designed by experts and cannot be automatically gained by using programs, which may limit the application of P systems. How to automatically design a P system by using programs, namely, the programmability of a P system, is an attractive research direction in the area of membrane computing [5]. The automatic design of a P system is a very complicated and challenging task. The related work in the literature focused on the use of evolutionary algorithms to make a population of P systems evolve toward a successful one. This ⋆Corresponding author. 2 W. Yuan, G. Zhang, M.J. P´erez-Jim´enez work started with 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 [6–9, 4]. In [6], a genetic algorithm was used to design a P system to calculate 42. In [7], a binary encoding technique was presented to denote an evolution rule set of a P system and a quantum-inspired evolutionary algorithm (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 [8], an evaluation approach considering non-determinism and halting penalty factors and a genetic algorithm with the binary encoding technique in [7] were introduced to design P systems for 42,n2and the generation of 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 [4, 9] by applying one pre-defined redundant evolution rule set to design multiple different P systems, each of which executes a computation task. In [9], 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 [4], a common redundant set of evolution rules was applied to design successful P systems for fulfilling eight computational tasks: 2(n−1), 2n−1, n2,1 2[(n−1)2+ (n−1)], (n−1)2+ (n−1), (n−1)2+ 2n+ 2, a2nb3nand 1 2(3n−1), (n > 1 or 2). A significant development in this topic is the work in [10] in which a cell-like halting P system for 42was designed by tuning membrane structures, initial objects and evolution rules. In this work, a genetic algorithm with a binary encoding technique was discussed to codify the membrane structure, initial objects and evolution rules of a P system. 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 [5]. 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 [5]. On the basis of the studies mentioned above, our aim is to design a P system to compute a general polynomial. This paper proposes a reasoning method to implement the design of a simple (deterministic transition) P system (without input membrane) of degree 1, capturing the value of the k-order polynomial, and it also presents the descriptive computational resources required by the designed k-order polynomial P system. The reasoning method is the use of the characteristics of P systems with a membrane structure, initial objects and rules, and the semantics of the P systems to provide a way to design the required P Systems based Computing Polynomials: Design and Formal Verification 3 membrane systems. The introduced technique is completely different from the previous work that used evolutionary algorithms to design a P system. The remainder of this paper is organized as follows: Section 2 describes the polynomials we aim to design. In Sections 3, the two-, three- and k-order polynomial P systems are designed. Section 4 discusses the descriptive computational resources that the two-, three- and k-order polynomial P systems require. Section 5 concludes this work. 2 Polynomials computed by P systems We start by defining what computing a k-order polynomial means in the framework of deterministic transition P system without input membrane. Definition 1. Let p(n)be a polynomial whose coeficients are natural numbers. We say that p(n)is computed by a deterministic transition P system without input membrane Πp(n)= (Γ, µ, M1, . . . , Mq,R1,...,Rq, iout), if the following holds: –There exists a distinguished object (the output object), o, in the working alphabet Γ. –For each t∈N, in the configuration Ctof Πp(n)at instant t, the multiplicity of object oin the output membrane labelled by iout is p(t). From the previous definition, if a deterministic transition P system without input membrane computes a polynomial, then the computation of that system is a non-halting computation. We try to find a minimum such P system computing a k-order polynomial. Here the concept “minimum” refers to the following constraints associated with P systems: –The membrane structure has only one membrane. –The evolution rules are non-cooperative. –The number of objects and rules must be minimum. 3 Polynomial P systems design 3.1 Two-order polynomial P system design In this section we present a (deterministic) transition P system (without input membrane), Πp(n), of degree 1 that computes the arbitrary polynomial with order 2, p(n) = a2·n2+a1·n+a0, where a0, a1, a2are natural numbers, in the sense of Definition 1. It is worth pointing out that p(n+ 1) = p(n)+2a2·n+a2+a1. 4 W. Yuan, G. Zhang, M.J. P´erez-Jim´enez For each symbol x, the expression x0denotes the empty multiset (or the empty string). Associated with the polynomial p(n) = a2·n2+a1·n+a0, we consider the (deterministic) transition P system (without input membrane) Πp(n)= (Γ, µ, M1,R1, iout) of degree 1, defined as follows: –Γ={b1, b2,o}and the output object is o; –µ= [ ]1; –M1={oa0b1}; –R1is the set of the following non-cooperative evolution rules: –r1≡[b1−→ oa2+a1b1b2]1; –r2≡[b2−→ o2a2b2]1. –iout = 1. Let C= (C0,C1,C2, . . . , Ct, . . . ) be the (unique) computation of Π. For each t∈N and x∈Γ, we denote by Ct(1) the multiset over Γassociated with the membrane 1 in configuration Ct. Theorem 1. For every t∈Nwe have Ct(1) = {op(t), b1, b2t}. Proof. Let us prove the result by induction on t. For the base case, t= 0, we note that C0(1) = M1={oa0b1}={op(0) , b1, b20}. Let us assume the result holds for t≥0, that is, let us suppose that Ct(1) = {op(t), b1, b2t}. In order to obtain Ct+1(1), we must apply the rules r1and r2 to configuration Ct. Then Ct+1(1) = {op(t),oa2+a1, b1, b2,o2a2·t, b2t} ={op(t)+2a2·t+a2+a1, b1, b2(t+1) } ={op(t+1) , b1, b2(t+1) } Hence, the result holds for t+ 1. Corollary 1. For every t∈N, in configuration Ctof Πp(n)at instant t, the multiplicity of object oin the membrane of the system is p(t). 3.2 Three-order polynomial P system design In this section we present a (deterministic) transition P system (without input membrane), Πp(n), of degree 1 that computes the arbitrary polynomial with order 3, p(n) = a3·n3+a2·n2+a1·n+a0, where a0, a1, a2, a3are natural numbers, in the sense of Definition 1. P Systems based Computing Polynomials: Design and Formal Verification 5 It is worth pointing out that p(n+1) = p(n)+3a3n2+(3a3+2a2)n+a3+a2+a1. Associated with the polynomial p(n) = a3·n3+a2·n2+a1·n+a0, we consider the (deterministic) transition P system (without input membrane), Πp(n)= (Γ, µ, M1, R1), of degree 1 defined as follows: –Γ={b1, b2, b3,o}and the output object is o; –µ= [ ]1; –M1={oa0b1}; –R1is the set of the following non-cooperative evolution rules: –r1≡[b1−→ oa3+a2+a1b1b2b3]1; –r2≡[b2−→ o3a3+2a2b2b32]1; –r3≡[b3−→ o3a3b3]1. Let C= (C0,C1,C2, . . . , Ct, . . . ) be the (unique) computation of Π. For each t∈N and x∈, Γ we denote by Ct(1) the multiset over Γassociated with membrane 1 in configuration Ct. Theorem 2. For every t∈Nwe have Ct(1) = {op(t), b1, b2t, b3t2}. Proof. Let us prove the result by induction on t. For the base case, t= 0, we note that C0(1) = M1={oa0b1}={op(0) , b1, b20, b302}. Let us assume the result holds for t≥0, that is, let us suppose that Ct(1) = {op(t), b1, b2t, b3t2}. In order to obtain Ct+1(1), we can apply the rules r1, r2 and r3to configuration Ct. Then Ct+1(1) = {op(t),oa3+a2+a1, b1, b2, b3,o(3a3+2a2)·t, b2t, b32t,o3a3t2, b3t2} ={op(t)+3a3t2+(3a3+2a2)t+a3+a2+a1, b1, b2t+1 , b3t2+2t+1} ={op(t+1) , b1, b2t+1 , b3(t+1)2} Hence, the result holds for t+ 1. Corollary 2. For every t∈N, in configuration Ctof Πp(n)at instant t, the multiplicity of object oin the membrane of the system is p(t). 3.3 k-order polynomial P system design In this section we present a (deterministic) transition P system (without input membrane), Πpk(n), of degree k≥1 that computes the arbitrary polynomial with order k,pk(n) = ak·nk+ak−1·nk−1+· · · +a1·n1+a0·n0, where ak, ak−1, . . . , a1, a0are natural numbers. It is worth pointing out that the increment pk(n+1)−pk(n) of polynomial pk(n) is: 6 W. Yuan, G. Zhang, M.J. P´erez-Jim´enez [(k 1)ak]·nk−1+[(k 2)ak+(k−1 1)ak−1]·nk−2+ [(k 3)ak+(k−1 2)ak−1+(k−2 1)ak−2]·nk−3+ ................................. [(k k−1)ak+(k−1 k−2)ak−1+· · · +(3 2)a3+(2 1)a2]·n1+ [(k k)ak+(k−1 k−1)ak−1+· · · +(2 2)a2+(1 1)a1]·n0 Let us denote: –α(0) k=(k k)ak+(k−1 k−1)ak−1+· · · +(2 2)a2+(1 1)a1 –α(1) k=(k k−1)ak+(k−1 k−2)ak−1+· · · +(3 2)a3+(2 1)a2 –α(2) k=(k k−2)ak+(k−1 k−3)ak−1+· · · +(4 2)a4+(3 1)a3 –α(3) k=(k k−3)ak+(k−1 k−4)ak−1+· · · +(5 2)a5+(4 1)a4 ................................. –α(k−1) k=(k 1)ak Then: pk(n+ 1) −pk(n) = α(0) k·t0+α(1) k·t+α(2) k·t2+· · · +α(k−1) k·tk−1 Associated with polynomial pk(n) = ak·nk+ak−1·nk−1+· · ·+a1·n1+a0·n0 of order k, we consider the (deterministic) transition P system (without input membrane) Πpk(n)= (Γ, µ, M1,R1) of degree 1, defined as follows: –Γ={o, b1, b2, . . . , bk}and the output object is o; –µ= [ ]1; –M1={oa0b1}; –R1is the set of the following non-cooperative evolution rules: –r1≡[b1−→ oα(0) kb(0 0) 1b(1 0) 2b(2 0) 3b(3 0) 4. . . b(k−1 0) k]1; –r2≡[b2−→ oα(1) kb(1 1) 2b(2 1) 3b(3 1) 4. . . b(k−1 1) k]1; –r3≡[b3−→ oα(2) kb(2 2) 3b(3 2) 4. . . b(k−1 2) k]1; –r4≡[b4−→ oα(3) kb(3 3) 4. . . b(k−1 3) k]1; ................................. P Systems based Computing Polynomials: Design and Formal Verification 7 –rk≡[bk−→ oα(k−1) kb(k−1 k−1) k]1; Let C= (C0,C1,C2, . . . , Ct, . . . ) the (unique) computation of Π. For each t∈N and x∈, Γ we denote by Ct(1) the multiset over Γassociated with the membrane 1 in configuration Ct. Theorem 3. For every t∈N, we have Ct(1) = {opk(t), b1, b2t, . . . , bktk−1}. Proof. Let us prove the result by induction on t. For the base case, t= 0, let us notice that C0(1) = M1={oa0b1}= {opk(0) , b1, b0 2, . . . , bk0}. Let us assume the result holds for t≥0, that is, let us suppose that Ct(1) = {opk(t), b1, b2t, . . . , bktk−1} In order to obtain Ct+1(1), we must apply the rules r1, r2and rkto configuration Ct. Then Ct+1(1) = {opk(t),oα(0) k+α(1) k ·t+α(2) k ·t2+···+α(k−1) k ·tk−1, b1, b2(1 0)+(1 1)·t, b3(2 0)+(2 1)·t(2 2)·t2 , . . . , bk(k−1 0)+(k−1 1)·t+···+(k−1 k−1)·tk−1} ={opk(t)+α(0) k+α(1) k ·t+α(2) k ·t2+···+α(k−1) k ·tk−1, b1, b2(t+1), b3(t+1)2, . . . , bk(t+1)k−1} ={opk(t+1), b1, b2(t+1), b3(t+1)2, . . . , bk(t+1)k−1} Hence, the result holds for t+ 1. Corollary 3. For every t∈N, in configuration Ctof Πpk(n)at instant t, the multiplicity of object oin the membrane of the system is pk(t). 4 Descriptive computational resources This section discusses the descriptive computational resources required by the designed two-, three- and k–order polynomial P systems. According to the design procedures of two- and three-order polynomial P systems, the amount of resources to build the designed P systems (of degree 1) in both cases are 2 rules and 3 objects, 3 rules and 4 objects, respectively. In what follows, we discuss the descriptive computational resources required by the designed k–order polynomial P system Πpk(n)of degree 1. –The size of the working alphabet k+ 1. –The initial number of objects: a0+ 1. –The number of rules: k. –The sum of total length of rules: 8 W. Yuan, G. Zhang, M.J. P´erez-Jim´enez Table 1. Resources of different order polynomial P systems. SWA, INO, NoR and SLR represent the size of the working alphabet, the initial number of objects, the number of rules and the sum of total length of rules, respectively. The symbol ‘–’ means that the result is not obtained. Two-order Three-order ... k-order SWA 3 4 ... k+1 INO a0+1 a0+1 ... a0+1 NoR 2 3 ... k SLR 3a2+a1+ 5 7a3+ 3a2+a1+ 10 ... LR(k) •Objects in the left-hand side: k. •Objects oin the right-hand side: α(0) k+α(1) k+α(2) k+· · · +α(k−1) k. That is, the total number of objects oin the rules is: (2k−1) ·ak+ (2k−1−1) ·ak−1+···+ (22−1) ·a2+ (21−1) ·a1 •Objects bj(1 ≤j≤k) in the right-hand side: (j−1 0)+(j−1 1)+· · · +(j−1 j−1) Thus, the total number of such kind of objects in the right hand side of the rules is: j=k ∑ j=1 [(j−1 0)+(j−1 1)+· · · +(j−1 j−1)]= j=k ∑ j=1 2j−1= 2k−1 Therefore, the sum of total length of rules is LR(k): LR(k) = k+(2k−1)·ak+(2k−1−1)·ak−1+· · ·+(22−1)·a2+(21−1)·a1+2k−1 Hence, the total amount of descriptive computational resources is exponential in the k–order polynomial. We summarize the amount of resources to build the designed P systems (of degree 1) as shown in Table 1, where SWA, INO, NoR and SLR represent the size of the working alphabet, the initial number of objects, the number of rules and the sum of total length of rules, respectively. In Table 1, the designed twoorder polynomial P system (Two-order, for short) is a2·n2+a1·n+a0; the designed three-order polynomial P system (Three-order, for short) is a3·n3+ a2·n2+a1·n+a0; the k-order polynomial P system (k-order, for short) is ak·nk+... +a1·n+a0. 5 Conclusion By analyzing the syntax and semantics of cell-like P systems, this study presented a reasoning method to design a k-order (k≥2) polynomial P system. P Systems based Computing Polynomials: Design and Formal Verification 9 The significance of this study is to provide an alternative approach to automatically design a P system that can perform a given task, which is different from the previous work on this topic. In future works, we really hope to extend this method to design more variants of P systems for more computational tasks. Our ambitious aim is to find a way to design the minimal P system for a given task including definite tasks such as the computation of polynomials and indefinite tasks like practical applications such as membrane controllers for mobile robots. Acknowledgment The work of W. Yuan, G. Zhang, T. Wang and Z. Huang is supported by the National Natural Science Foundation of China (61170016, 61373047). The work of M.J. P´erez-Jim´enez is supported by Project TIN2012-37434 of the Ministerio de Econom´ıa y Competitividad of Spain. References 1. Gh. P˘aun. Computing with membranes, Journal of Computer and System Sciences, vol. 61, pp. 108–43 (2000) (first circulated at TUCS Research Report No 208, November 1998, http://www.tucs.fi)). 2. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds. The Oxford Handbook of Membrane Computing, Oxford University Press, New York, 2010. 3. G. Zhang, J. Cheng, T. Wang, X. Wang, J. Zhu. Membrane Computing: Theory and Applications, Science Press, Beijing, 2015. 4. G. Zhang, M. Gheorghe, L. Pan, M.J. P´erez-Jim´enez. Evolutionary membrane computing: a comprehensive survey and new results. Information Sciences, 279, 528–551 (2014). 5. G. Zhang, H. Rong, Z. Ou, M.J. P´erez-Jim´enez, M. Gheorghe. Automatic Design of Deterministic and Non-Halting Membrane Systems by Tuning Syntactical Ingredients. IEEE Transactions on Nanobioscience, 13(3): 363–371 (2014). 6. G. Escuela, M.A. Guti´errez-Naranjo. An application of genetic algorithms to membrane computing, in M.A. Mart´ınez del Amor, Gh. P˘aun, I. P´erez Hurtado, A. Riscos (eds.) Proceedings of the Eighth Brainstorming Week on Membrane Computing, Seville, Spain, February 1-5, 2010, Report RGNC 01/2010, F´enix Editora, 2010, pp. 101-108. 7. X. Huang, G. Zhang, H. Rong, F. Ipate. Evolutionary design of a simple membrane system. Lecture Notes in Computer Science (CMC2011), vol. 7184, 2012, pp. 203– 14. 8. C. Tudose, R. Lefticaru, F. Ipate. Using genetic algorithms and model checking for P systems automatic design, Studies in Computational Intelligence (NICSO2011), vol. 387, 2011, pp. 285–302. 9. Y. Chen, G. Zhang, T. Wang, X. Huang. Automatic design of a P system for basic arithmetic operations, Chinese Journal of Electronics, 23(2): 302–304 (2014). 10. Z. Ou, G. Zhang, T. Wang, and X. Huang. Automatic design of cell-like P systems through tuning membrane structures, initial objects and evolution rules, International Journal of Unconventional Computing, 9(5-6), 425–443 (2013).