P Systems with Rule Production and Removal

• Autorzy: Pan Linqiang , Song Bosheng

Identyfikatory

DOI

10.3233/FI-2020-1885

• Języki publikacji: EN

Abstrakty

EN

P systems are a class of parallel computational models inspired by the structure and functioning of living cells, where all the evolution rules used in a system are initially set up and keep unchanged during a computation. In this work, inspired by the fact that chemical reactions in a cell can be affected by both the contents of the cell and the environmental conditions, we introduce a variant of P systems, called P systems with rule production and removal (abbreviated as RPR P systems), where rules in a system are dynamically changed during a computation, that is, at any computation step new rules can be produced and some existing rules can be removed. The computational power of RPR P systems and catalytic RPR P systems is investigated. Specifically, it is proved that catalytic RPR P systems with one catalyst and one membrane are Turing universal; for purely catalytic RPR P systems, one membrane and two catalysts are enough for reaching Turing universality. Moreover, a uniform solution to the SAT problem is provided by using RPR P systems with membrane division. It is known that standard catalytic P systems with one catalyst and one membrane are not Turing universal. These results imply that rule production and removal is a powerful feature for the computational power of P systems.

Słowa kluczowe

EN

bio-inspired computing; catalytic P system; membrane computing; SAT problem; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 313--329
• Opis fizyczny: Bibliogr. 51 poz.

Twórcy

autor

Pan Linqiang

• School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China
• School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China

autor

Song Bosheng

• College of Information Science and Engineering, Hunan University, Changsha 410082, Hunan, China

Bibliografia

• [1] Păun Gh. Computing with membranes, Journal of Computer and System Sciences, 2000, 61(1):108-143. URL https://doi.org/10.1006/jcss.1999.1693.
• [2] Song B, Song T, Pan L. A time-free uniform solution to subset sum problem by tissue P systems with cell division, Mathematical Structures in Computer Science, 2017, 27(1):17-32. doi:10.1017/ S0960129515000018.
• [3] Song B, Zhang C, Pan L. Tissue-like P systems with evolutional symport/antiport rules, Information Sciences, 2017, 378:177-193. URL https://doi.org/10.1016/j.ins.2016.10.046.
• [4] Wu T, Păun A, Zhang Z, Pan L. Spiking neural P systems with polarizations, IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(8):3349-3360. doi:10.1109/TNNLS.2017.2726119.
• [5] Zhang Z, Su Y, Pan L. The computational power of enzymatic numerical P systems working in the sequential mode, Theoretical Computer Science, 2018, 724:3-12. URL https://doi.org/10.1016/j.tcs.2017.12.016.
• [6] Wu T, Zhang Z, Păun Gh, Pan L. Cell-like spiking neural P systems, Theoretical Computer Science, 2016, 623(C):180-189. doi:10.1016/j.tcs.2015.12.038.
• [7] Zhang Z, Wu T, Păun A, Pan L. Universal enzymatic numerical P systems with small number of enzymatic variables, Science China Information Sciences, 2018, 61(9):092103. doi:10.1007/s11432-017-9103-5.
• [8] Alhazov A, Freund R. Variants of small universal P systems with catalysts, Fundamenta Informaticae, 2015, 138(1-2):227-250. doi:10.3233/FI-2015-1209.
• [9] Pan L, Song B, Valencia-Cabrera L, Pérez-Jiménez MJ. The computational complexity of tissue P systems with evolutional symport/antiport rules, Complexity, 2018, pp. 21. URL https://doi.org/10.1155/2018/3745210.
• [10] Song B, Pérez-Jiménez MJ, Pan L. An efficient time-free solution to QSAT problem using P systems with proteins on membranes, Information and Computation, 2017, 256:287-299. URL https://doi.org/10.1016/j.ic.2017.06.005.
• [11] Díaz-Pernil D, Peña-Cantillana F, Gutiérrez-Naranjo MA. A parallel algorithm for skeletonizing images by using spiking neural P systems, Neurocomputing, 2013, 115:81-91. URL https://doi.org/10.1016/j.neucom.2012.12.032.
• [12] Peng H, Wang J, Pérez-Jiménez MJ, Riscos-Núñez A. An unsupervised learning algorithm for membrane computing, Information Sciences, 2015, 304:80-91. URL https://doi.org/10.1016/j.ins.2015.01.019.
• [13] Zhang G, Rong H, Neri F, Pérez-Jiménez MJ. An optimization spiking neural P system for approximately solving combinatorial optimization problems, International Journal of Neural Systems, 2014, 24(5):1-16. URL https://doi.org/10.1142/S0129065714400061.
• [14] Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, Riscos-Núñez A, Pérez-Jiménez MJ. Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes, Fundamenta Informaticae, 2017, 153(1-2):147-172. doi:10.3233/FI-2017-1535.
• [15] Song B, Hu Y, Adorna HN, Xu F. A quick survey of tissue-like P systems, Romanian Journal of Information Science and Technology, 2018, 21(3):310-321. URL https://www.romjist.ro/full-texts/paper603.pdf.
• [16] Martín-Vide C, Pazos J, Păun Gh, Rodríguez-Patón A. Tissue P systems, Theoretical Computer Science, 2003, 296(2):295-326. URL https://doi.org/10.1016/S0304-3975(02)00659-X.
• [17] Alhazov A, Fernau H, Freund R, Ivanov S, Siromoney R, Subramanian KG. Contextual array grammars with matrix control, regular control languages, and tissue P systems control, Theoretical Computer Science, 2017, 682:5-21. URL https://doi.org/10.1016/j.tcs.2017.03.012.
• [18] Song B, Pan L, Pérez-Jiménez MJ. Tissue P systems with protein on cells, Fundamenta Informaticae, 2016, 144(1):77-107. doi:10.3233/FI-2016-1324.
• [19] Ionescu M, Păun Gh, Yokomori T. Spiking neural P systems, Fundamenta Informaticae, 2006, 71(2-3):279-308. URL https://content.iospress.com/articles/fundamenta-informaticae/fi71-2-3-08.
• [20] Wu T, Bîlbîe F, Păun A, Pan L, Neri F. Simplified and yet Turing universal spiking neural P systems with communication on request, International Journal of Neural Systems, 2018, 28(8):1850013. doi:10.1142/S0129065718500132.
• [21] Pan L, Păun Gh, Zhang G, Neri F. Spiking neural P systems with communication on request, International Journal of Neural Systems, 2017, 27(8):1750042. URL https://doi.org/10.1142/S0129065717500423.
• [22] Păun Gh. Membrane Computing. An Introduction, Springer-Verlag, Berlin, Heidelberg, 2002. doi:10.1007/978-3-642-56196-2.
• [23] Păun Gh, Rozenberg G, Salomaa A. (Eds.) The Oxford Handbook of Membrane Computing, Oxford University Press, New York, USA, 2010. ISBN:0199556679 9780199556670.
• [24] Ionescu M, Martín-Vide C, Păun A, Păun Gh. Unexpected universality results for three classes of P systems with symport/antiport, Natural Computing, 2003, 2(4):337-348. doi:10.1023/B:NACO.0000006773.31625.55.
• [25] Martín-Vide C, Păun A, Păun Gh. On the power of P systems with symport rules, Journal of Universal Computer Science, 2002, 8:317-331. doi:10.3217/jucs-008-02-0317.
• [26] Păun A, Păun Gh. The power of communication: P systems with symport/antiport, New Generation Computing, 2002, 20(3):295-305. doi:10.1007/BF03037362.
• [27] Ferretti C, Mauri G, Păun Gh, Zandron C. On three variants of rewriting P systems, Theoretical Computer Science, 2003, 301(1-3):201-215. URL https://doi.org/10.1016/S0304-3975(02)00581-9.
• [28] Krishna SN. On pure catalytic P systems, Lecture Notes in Computer Science, 2006, 4135:152-165. doi:10.1007/11839132_13.
• [29] Sosík P, Langer M. Small (purely) catalytic P systems simulating register machines, Theoretical Computer Science, 2016, 623:65-74. URL https://doi.org/10.1016/j.tcs.2015.09.020.
• [30] Sosík P. The power of catalysts and priorities in membrane systems, Grammars, 2003, 6(1):13-24. doi:10.1023/A:1024057002599.
• [31] Sosík P, Freund R. P systems without priorities are computationally universal, Lecture Notes in Computer Science, 2003, 2597:400-409. doi:10.1007/3-540-36490-0_28.
• [32] Freund R, Kari L, Oswald M, Sosík P. Computationally universal P systems without priorities: two catalysts are sufficient, Theoretical Computer Science, 2005, 330(2):251-266. URL https://doi.org/10.1016/j.tcs.2004.06.029.
• [33] Freund R, Sosík P. On the power of catalytic P systems with one catalyst, Lecture Notes in Computer Science, 2015, 9504:137-152. doi:10.1007/978-3-319-28475-0_10.
• [34] Păun Gh. Some open problems about catalytic, numerical and spiking neural P systems, Lecture Notes in Computer Science, 2014, 8340:33-39. doi:10.1007/978-3-642-54239-8_4.
• [35] Wu T, Zhang Z, Păun Gh, Pan L. On the universality of colored one-catalyst P systems, Fundamenta Informaticae, 2016, 144(2):205-212. doi:10.3233/FI-2016-1328.
• [36] Ibarra OH, Dang Z, Egecioglu O. Catalytic P systems, semilinear sets, and vector addition systems, Theoretical Computer Science, 2004, 312(2-3):379-399. URL https://doi.org/10.1016/j.tcs.2003.10.028.
• [37] Ibarra OH, Dang Z, Egecioglu O, Saxena G. Characterizations of catalytic membrane computing systems, Lecture Notes in Computer Science, 2003, 2747:480-489. doi:10.1007/978-3-540-45138-9_42.
• [38] Arroyo F, Baranda AV, Castellanos J, Păun Gh. Membrane computing: The power of (rule) creation, Journal of Universal Computer Science, 2002, 8(3):369-381. doi:10.3217/jucs-008-03-0369.
• [39] Alhazov A, Freund R, Heikenwälder H, Oswald M, Rogozhin Y, Verlan S. Sequential P systems with regular control, Lecture Notes in Computer Science, 2013, 7762:112-127. doi:10.1007/978-3-642-36751-9_9.
• [40] Rozenberg G, Salomaa A. (Eds.) Handbook of Formal Languages, 3 vols., Springer-Verlag, Berlin, Heidelberg, 1997. doi:10.1007/978-3-642-59136-5.
• [41] Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F. A polynomial complexity class in P systems using membrane division, Journal of Automata, Languages and Combinatorics, 2006, 11:423-434. doi:10.25596/jalc-2006-423.
• [42] Minsky ML. Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, USA, 1967. ISBN:0-13-165563-9.
• [43] Garey MR, Johnson DJ. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, USA, 1979. ISBN:0716710447.
• [44] Song B, Pan L, Pérez-Jiménez MJ. Cell-like P systems with channel states and symport/antiport rules, IEEE Transactions on NanoBioscience, 2016, 15(6):555-566. doi:10.1109/TNB.2016.2594192.
• [45] Macías-Ramos LF, Song B, Valencia-Cabrera L, Pan L, Pérez-Jiménez MJ. Membrane fission: a computational complexity perspective, Complexity, 2016, 21:321-334. URL https://doi.org/10.1002/cplx.21691.
• [46] Pan L, Pérez-Jiménez MJ. Computational complexity of tissue-like P systems, Journal of Complexity, 2010, 26(3):296-315. URL https://doi.org/10.1016/j.jco.2010.03.001.
• [47] Freund R, Verlan S. (Tissue) P systems working in the k-restricted minimally or maximally parallel transition mode, Natural Computing, 2011, 10(2):821-833. doi:10.1007/s11047-010-9215-z.
• [48] Verlan S, Quiros J. Fast hardware implementations of P systems, Lecture Notes in Computer Science, 2013, 7762:404-423. doi:10.1007/978-3-642-36751-9_27.
• [49] Pan L, Păun Gh, Song B. Flat maximal parallelism in P systems with promoters, Theoretical Computer Science, 2016, 623:83-91. URL https://doi.org/10.1016/j.tcs.2015.10.027.
• [50] Song B, Pérez-Jiménez MJ, Păun Gh, Pan L. Tissue P systems with channel states working in the flat maximally parallel way, IEEE Transactions on NanoBioscience, 2016, 15(7):645-656. doi:10.1109/TNB.2016.2594380.
• [51] Song B, Kong Y. Solution to PSPACE-complete problem using P systems with active membranes with time-freeness, Mathematical Problems in Engineering, 2019, pp. 8. URL https://doi.org/ 10.1155/2019/5793234.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).