SCIENCE CHINA Information Sciences, Volume 61 , Issue 9 : 092103(2018) https://doi.org/10.1007/s11432-017-9103-5

Universal enzymatic numerical P systems with small number of enzymatic variables

More info
  • ReceivedJan 26, 2017
  • AcceptedApr 20, 2017
  • PublishedNov 20, 2017


Numerical P systems (for short, NP systems) are distributed and parallel computing models inspired from the structure of living cells and economics. Enzymatic numerical P systems (for short, ENP systems) are a variant of NP systems, which have been successfully applied in designing and implementing controllers for mobile robots. Since ENP systems were proved to be Turing universal, there has been much work to simplify the universal systems, where the complexity parameters considered are the number of membranes, the degrees of polynomial production functions or the number of variables used in the systems. Yet the number of enzymatic variables, which is essential for ENP systems to reach universality, has not been investigated. Here we consider the problem of searching for the smallest number of enzymatic variables needed for universal ENP systems. We prove that for ENP systems as number acceptors working in the all-parallel or one-parallel mode, one enzymatic variable is sufficient to reach universality; while for the one-parallel ENP systems as number generators, two enzymatic variables are sufficient to reach universality. These results improve the best known results that the numbers of enzymatic variables are $13$ and $52$ for the all-parallel and one-parallel systems, respectively.


This work was supported by National Natural Science Foundation of China (Grant Nos. 61772214, 61320106005, 61033003, 61472154) and Innovation Scientists and Technicians Troop Construction Projects of Henan Province (Grant No. 154200510012). The work of Andrei Pu aun was supported by UEFSCDI Project RemoteForest Project (Grant No. PN-II-PTPCCA-2011-3.2-1710). This paper was written during a three-months stay of Zhiqiang Zhang and Tingfang Wu in Curtea de Argec s, Romania, in the fall of 2015.


[1] Rozenberg G, Bäck T, Kok J N. Handbook of Natural Computing. Berlin: Springer, 2012. Google Scholar

[2] Miller W T, Werbos P J, Sutton R S. Neural Networks for Control. Cambridge: MIT Press, 1995. Google Scholar

[3] P?un G. Computing with Membranes. J Comput Syst Sci, 2000, 61: 108-143 CrossRef Google Scholar

[4] Păun G, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing. New York: Oxford University Press, 2010. Google Scholar

[5] Păun G. Membrane Computing: An Introduction. Berlin: Springer, 2012. Google Scholar

[6] Ciobanu G, Păun G, Pérez-Jiménez M J. Applications of Membrane Computing. Berlin: Springer, 2006. Google Scholar

[7] Frisco P, Gheorghe M, Pérez-Jiménez M J. Applications of Membrane Computing in Systems and Synthetic Biology. Berlin: Springer, 2014. Google Scholar

[8] Alhazov A, Sburlan D. Static sorting P systems. In: Applications of Membrane Computing. Berlin: Springer, 2006. 215--252. Google Scholar

[9] Nishida T Y. An approximate algorithm for NP-complete optimization problems exploiting P systems. In: Proceedings of the 1st Brainstorming Workshop on Uncertainty in Membrane Computing, Palma de Mallorca, 2004. 185--192. Google Scholar

[10] Nishida T Y. Membrane algorithms: approximate algorithms for NP-complete optimization problems. In: Applications of Membrane Computing. Berlin: Springer, 2006. 303--314. Google Scholar

[11] Enguix G B. Unstable P systems: applications to linguistics. Lect Notes Comput Sci, 2005, 3365: 190--209. Google Scholar

[12] Michel O, Jacquemard F. An analysis of a public key protocol with membranes. In: Applications of Membrane Computing. Berlin: Springer, 2006. 283--302. Google Scholar

[13] Dinneen M J, Kim Y B, Nicolescu R. P systems and the Byzantine agreement. J Logic Algebraic Programming, 2010, 79: 334-349 CrossRef Google Scholar

[14] Colomer M, Montori A, García E. Using a bioinspired model to determine the extinction risk of Calotriton asper populations as a result of an increase in extreme rainfall in a scenario of climatic change. Ecol Model, 2014, 281: 1-14 CrossRef Google Scholar

[15] Margalida A, Colomer M. Modelling the effects of sanitary policies on European vulture conservation. Sci Rep, 2012, 2: 753 CrossRef PubMed ADS Google Scholar

[16] Ionescu M, Păun G, Yokomori T. Spiking neural P systems. Fund Inform, 2006, 71: 279--308. Google Scholar

[17] Peng H, Wang J, Pérez-Jiménez M J. Fuzzy reasoning spiking neural P system for fault diagnosis. Inf Sci, 2013, 235: 106-116 CrossRef Google Scholar

[18] Xiangxiang Zeng , Tao Song , Xingyi Zhang . Performing four basic arithmetic operations with spiking neural P systems.. IEEE Transon NanoBiosci, 2012, 11: 366-374 CrossRef PubMed Google Scholar

[19] Zhang G, Cheng J, Wang T, et al. Membrane Computing: Theory & Applications (in Chinese). Beijing: Science Press, 2015. Google Scholar

[20] Zhang G, Rong H, Neri F, et al. An optimization spiking neural P system for approximately solving combinatorial optimization problems. Int J Neural Syst, 2014, 24: 1--16. Google Scholar

[21] Păun G, Păun R. Membrane computing and economics: numerical P systems. Fund Inform, 2006, 73: 213--227. Google Scholar

[22] Rivera D L, Naranjo M Á G. The pole balancing problem with enzymatic numerical P systems. In: Proceedings of the 13th Brainstorming Week on Membrane Computing, Sevilla, 2015. 195--206. Google Scholar

[23] Buiu C, Vasile C, Arsene O. Development of membrane controllers for mobile robots. Inf Sci, 2012, 187: 33-51 CrossRef Google Scholar

[24] Wang X, Zhang G, Neri F. Design and implementation of membrane controllers for trajectory tracking of nonholonomic wheeled mobile robots. ICA, 2015, 23: 15-30 CrossRef Google Scholar

[25] Arsene O, Buiu C, Popescu N. Snups---a simulator for numerical membrane computing. Int J Innov Comput Inform Control, 2011, 7: 3509--3522. Google Scholar

[26] Buiu C, Arsene O, Cipu C. A software tool for modeling and simulation of numerical P systems.. Biosystems, 2011, 103: 442-447 CrossRef PubMed Google Scholar

[27] Pavel A B. Membrane controllers for cognitive robots. Dissertation for M.S. Degree. Bucharest: University of Bucharest, 2011. Google Scholar

[28] Garc'ıa-Quismondo M, Pavel A B, Pérez-Jiménez M d J, et al. Simulating large-scale ENPS models by means of GPU. In: Proceedings of the 10th Brainstorming Week on Membrane Computing, Sevilla, 2012. 137--152. Google Scholar

[29] Pavel A, Arsene O, Buiu C. Enzymatic numerical P systems---a new class of membrane computing systems. In: Proceedings of IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), Liverpool, 2010. 1331--1336. Google Scholar

[30] Leporati A, Mauri G, Porreca A E, et al, Enzymatic numerical P systems using elementary arithmetic operations. In: Proceedings of the 14th International Conference on Membrane Computing, Moldova, 2016. 249--264. Google Scholar

[31] Leporati A, Porreca A E, Zandron C, et al. Improved universality results for parallel enzymatic numerical P systems. Int J Unconv Comput, 2013, 9: 385--404. Google Scholar

[32] Ioan Vasile C, Brandu?a Pavel A, Dumitrache I. Universality of Enzymatic Numerical P systems. Int J Comput Math, 2013, 90: 869-879 CrossRef Google Scholar

[33] Vasile C I, Pavel A B, Dumitrache I. On the power of enzymatic numerical P systems. Acta Informatica, 2012, 49: 395-412 CrossRef Google Scholar

[34] Păun G. Some open problems about catalytic, numerical, and spiking neural P systems. In: Proceedings of Revised Selected Papers of the 14th International Conference on Membrane Computing, Chic sinu au, 2013. 33--39. Google Scholar

[35] Minsky M L. Computation: Finite and Infinite Machines. Englewood Cliffs: Prentice-Hall, 1967. Google Scholar

[36] Zhang Z, Pan L. Numerical P Systems with Thresholds. INT J COMPUT COMMUN, 2016, 11: 292-304 CrossRef Google Scholar

[37] Zhang Z, Wu T, P?un A. Numerical P systems with migrating variables. Theor Comput Sci, 2016, 641: 85-108 CrossRef Google Scholar

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号