The Computational Power of Cell-like P Systems with Symport/Antiport Rules and Promoters

• Autorzy: Jiang Suxia , Wang Yanfeng , Xu Jinbang , Xu Fei

Identyfikatory

DOI

10.3233/FI-2019-1763

• Języki publikacji: EN

Abstrakty

EN

Cell-like P systems with symport/antiport rules (CSA P systems, for short) are a class of computational models in membrane computing, inspired by the way of transmembrane transport of substances through membrane channels between neighboring regions in a cell. In this work, we propose a variant of CSA P systems, called cell-like P systems with symport/antiport rules and promoters (CSAp P systems, for short), where symport/antiport rules are regulated by multisets of promoters. The computational power of CSAp P systems is investigated. Specifically, it is proved that CSAp P systems working in the maximally parallel mode, having arbitrary large number of membranes and promoters and using only symport rules of length 1 or antiport rules of length 2, are able to compute only finite sets of non-negative integers. Furthermore, we show that CSAp P systems with two membranes working in a sequential mode when having at most two promoters and using only symport rules of length 2, or having at most one promoter and using symport rules of length 1 and antiport rules of length 2, are Turing universal.

Słowa kluczowe

EN

bio-inspired computing; cell-like P system; membrane computing; promoter; symport/antiport rule; universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 2-3
• Strony: 207--225
• Opis fizyczny: Bibliogr. 42 poz., rys., tab.

Twórcy

autor

Jiang Suxia

• Henan Key Lab of Information-Based Electrical Appliances, Zhengzhou University of Light Industry, Zhengzhou 450002, Henan, China

autor

Wang Yanfeng

• Henan Key Lab of Information-Based Electrical Appliances, Zhengzhou University of Light Industry, Zhengzhou 450002, Henan, China

autor

Xu Jinbang

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

autor

Xu Fei

• Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China

Bibliografia

• [1] Păun Gh. Computing with Membranes. Journal of Computer and System Sciences, 2000;61(1):108-143. doi:10.1006/jcss.1999.1693.
• [2] Ciobanu G, Păun Gh, Pérez-Jiménez, MJ. Applications of Membrane Computing. Springer-Verlag, Berlin, 2005. ISBN 978-3-540-25017-3. doi:10.1007/3-540-29937-8.
• [3] Păun Gh. Membrane Computing: an Introduction. Springer Science & Business Media, Berlin, 2002. ISBN 3540436014. URL http://dl.acm.org/citation.cfm?id=581822.
• [4] 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. doi:10.1016/S0304-3975(02)00659-X.
• [5] Ionescu M, Păun Gh, Yokomori T. Spiking Neural P Systems. Fundamenta Informaticae. 2006;71(2,3):279-308. URL http://content.iospress.com/articles/fundamenta-informaticae/fi71-2-3-08.
• [6] Zhang XY, Pan LQ, Păun A. On the Universality of Axon P Systems. IEEE Transactions on Neural Networks and Learning Systems. 2015;26(11):2816-2829. doi:10.1109/TNNLS.2015.2396940.
• [7] Song T, Pan LQ. Spiking Neural P Systems with Request Rules. Neurocomputing. 2016;193:193-200. doi:10.1016/j.neucom.2016.02.023.
• [8] Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Shallow Non-confluent P Systems. In: Proceedings of the 17th International Conference on Membrane Computing, Italy, 2016 pp. 307-316. ISBN 978-3-319-54072-6. doi:10.1007/978-3-319-54072-6_19.
• [9] Wu TF, Zhang ZQ, Păun Gh, Pan LQ. Cell-like Spiking Neural P Systems. Theoretical Computer Science. 2016;623:180-189. doi:10.1016/j.tcs.2015.12.038.
• [10] Díaz-Pernil D, Gutierrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A. Solving the Independent Set Problem by Using Tissue-like P Systems with Cell Division. In: Third International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2009, Santiago de Compostela, Spain, 2009 pp. 213-222. ISBN 978-3-642-02264-7. doi:10.1007/978-3-642-02264-7_23.
• [11] Zandron C, Leporati A, Ferretti C, Mauri G, Pérez-Jiménez MJ. On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution. Fundamenta Informaticae. 2008;87(1):79-91. URL http://content.iospress.com/articles/fundamenta-informaticae/fi87-1-06.
• [12] Ciobanu G, Păun Gh, Pérez-Jiménez MJ. Applications of Membrane Computing. Springer-Verlag, Berlin, 2005. ISBN 978-3-540-29937-0. doi:10.1007/3-540-29937-8.
• [13] Frisco P, Gheorghe M, Pérez-Jiménez MJ. Applications of Membrane Computing in Systems and Synthetic Biology. Springer, Berlin, 2014. ISBN 978-3-319-03191-0. doi:10.1007/978-3-319-03191-0.
• [14] 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. doi:10.1016/j.ins.2015.01.019.
• [15] Peng H, Wang J, Shi P, Riscos-Núñez A, Pérez-Jiménez, M.J. An Automatic Clustering Algorithm Inspired by Membrane Computing. Pattern Recognition Letters. 2015;1(68):34-40. doi:10.1016/j.patrec.2015.08.008.
• [16] Wang J, Shi P, Peng H. Membrane Computing Model for IIR Filter Design. Information Sciences. 2016;329:164-176. doi:10.1016/j.ins.2015.09.011.
• [17] Zhang GX, Pérez-Jiménez MJ, Gheorghe M. Real-life Applications with Membrane Computing. Springer, Cham, 2017. ISBN 978-3-319-55989-6. doi:10.1007/978-3-319-55989-6.
• [18] Zhang GX, Pérez-Jiménez MJ, Gheorghe M. Data Modeling with Membrane Systems: Applications to Real Ecosystems. Real-life Applications with Membrane Computing. 2017 pp. 259-355. ISBN 978-3-319-55989-6. doi:10.1007/978-3-319-55989-6.
• [19] 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.
• [20] Alhazov A, Rogozhin Y. Minimal Cooperation in Symport/Antiport P Systems with One Membrane. In: 2013 Proceedings of the Third Brainstorming Week on Membrane Computing, Sevilla, 2013 pp. 29-34. ISBN 84-609-6771-9. URL http://hdl.handle.net/11441/36534.
• [21] Păun Gh, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc. New York, 2010. ISBN 0199556679 9780199556670. URL http://dl.acm.org/citation.cfm?id=SERIES13228.1738939.
• [22] Cavaliere M. Evolution-Communication P Systems. In: Proceedings International Workshop Membrane Computing, WMC 2002, Lecture Notes in Computer Science, 2597, Springer-Verlag, Berlin, 2003 pp. 134-145. ISBN 978-3-540-36490-0. doi:10.1007/3-540-36490-0_10.
• [23] Song BS, Pan LQ, 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.
• [24] Bottoni P, Martín-Vide C, Păun Gh, Rozenberg G. Membrane Systems with Promoters/Inhibitors. Acta Informatica. 2002;10(38):695-720. doi:10.1007/s00236-002-0090-7.
• [25] Pan LQ, Păun Gh, Song BS. Flat Maximal Parallelism in P Systems with Promoters. Theoretical Computer Science. 2016;623:83-91. doi:10.1016/j.tcs.2015.10.027.
• [26] Song BS, Pan LQ. The Computational Power of Tissue-like P Systems with Promoters. Theoretical Computer Science. 2016;641:43-52. doi:10.1016/j.tcs.2016.05.022.
• [27] Song BS, Pan LQ. Spiking Neural P Systems with Rules on Synapses Working in Maximum Spiking Strategy. IEEE transactions on nanobioscience. 2015;14(4):465-477. doi:10.1109/TNB.2015.2402311.
• [28] Song T, Pan LQ. Spiking Neural P Systems with Rules on Synapses Working in Maximum Spikes Consumption Strategy. IEEE transactions on nanobioscience. 2016;14(1):38-44. doi:10.1109/TNB.2015.2402311.
• [29] Ciobanu G, Pan LQ, Păun Gh, Pérez-Jiménez MJ. P Systems with Minimal Parallelism. Theoretical Computer Science. 2007;378(1):117-130. doi:10.1016/j.tcs.2007.03.044.
• [30] Freund R. Asynchronous P Systems and P Systems Working in the Sequential Mode. In: Membrane Computing. WMC 2004. Lecture Notes in Computer Science, 3365. Springer, Berlin, 2004 pp. 36-62. ISBN 978-3-540-31837-8. doi:10.1007/978-3-540-31837-8_3.
• [31] Freund R, Oswald M. Modelling Grammar Systems by Tissue P Systems Working in the Sequential Mode. Fundamenta Informaticae. 2007;76(3):305-323. URL http://content.iospress.com/articles/fundamentainformaticae/fi76-3-07.
• [32] Jiang KQ, Pan LQ. Spiking Neural P Systems with Anti-spikes Working in Sequential Mode Induced by Maximum Spike Number. Neurocomputing. 2016;171:1674-1683. doi:10.1016/j.neucom.2015.07.100.
• [33] Frisco P, Govan G, Leporati A. Asynchronous P Systems with Active Membranes. Theoretical Computer Science. 2012;429:74-86. doi:10.1016/j.tcs.2011.12.026.
• [34] Pan LQ, Wang YF, Jiang SX, Song BS. Flat Maximal Parallelism in Tissue P Systems with Promoters. Romanian Journal of Information Science and Technology. 2017;20(1):42-56. URL http://www.romjist.ro/content/pdf/paper4.pdf.
• [35] Rozenberg G, Salomaa A. Handbook of Formal Languages: Tree Languages. Springer, Berlin, 1997. ISBN 978-3-642-59126-6. doi:10.1007/978-3-642-59126-6_1.
• [36] Dassow J, Păun Gh. On the Power of Membrane Computing. Turku Centre for Computer Science, TUCS Technical Report No 217, 1998. ISBN 952-12-0330-7. URL http://dl.acm.org/citation.cfm?id=893177.
• [37] Korec I. Small Universal Register Machines. Theoretical Computer Science. 1996;168(2):267-301. doi:10.1016/S0304-3975(96)00080-1.
• [38] Minsky ML. Computation: Finite and Infinite Machines. Prentice-Hall, Inc. Upper Saddle River, NJ, 1967. ISBN 0-13-165563-9. URL http://dl.acm.org/citation.cfm?id=1095587.
• [39] Freund R, Ibarra OH, Păun Gh, Yen HC. Matrix Languages, Register Machines, Vector Addition Systems. In: Proceedings of the Third Brainstorming Week on Membrane Computing, Sevilla, 2005 pp. 155-167. ISBN 84-609-6771-9. URL http://hdl.handle.net/11441/36776.
• [40] Song BS, Zhang C, Pan LQ. Tissue-like P Systems with Evolutional Symport/Antiport Rules. Information Sciences. 2017;378:177-193. doi:10.1016/j.ins.2016.10.046.
• [41] Song BS, Pérez-Jiménez MJ, Pan LQ. An Efficient Time-free Solution to SAT Problem by P Systems with Proteins on Membranes. Journal of Computer and System Sciences. 2016;6(82):1090-1099. doi:10.1016/j.jcss.2016.03.008.
• [42] Song BS, Pérez-Jiménez MJ, Pan LQ. An Efficient Time-free Solution to QSAT Problem Using P Systems with Proteins on Membranes. Information and Computation. 2017;256:287-299. doi:10.1016/j.ic.2017.06.005.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).