Communication P Systems with Channel States Working in Flat Maximally Parallel Manner

• Autorzy: Jiang Suxia , Wang Yanfeng , Xu Fei , Deng Junli

Identyfikatory

DOI

10.3233/FI-2019-1821

• Języki publikacji: EN

Abstrakty

EN

Communication P systems with channel states (CC P systems, for short) are a class of distributed parallel computing models, where communication (symport/antiport) rules associated with channel states are executed in a sequential manner on membrane channels. In this work, communication P systems with channel states working in flat maximally parallel manner are considered and the computational power is investigated. Specifically, it is proved that communication P systems with channel states using symport rules of length two are Turing universal when having one membrane and any number of channel states, or two membranes and three channel states. Furthermore, membrane division is introduced into communication P systems with channel states, communication P systems with channel states and membrane division (CCD P systems, for short) are proposed. We provide a uniform solution to the Hamiltonian path problem (HPP) by CCD P systems working in a flat maximally parallel manner.

Słowa kluczowe

EN

bio-inspired computing; membrane computing; cell-like P system; symport rule; antiport rule; channel state; flat maximal parallelism

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 168, nr 1
• Strony: 1--24
• Opis fizyczny: Bibliogr. 56 poz., rys.

Twórcy

autor

Jiang Suxia

• School of Electrical and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou, 450002, Henan, China

autor

Wang Yanfeng

• School of Electrical and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou, 450002, Henan, China

autor

Xu Fei

• School of Automation, Huazhong University of Science and Technology, Wuhan, 430074, Hubei, China

autor

Deng Junli

• School of Information Science, Huazhong University of Agriculture, Wuhan, 430070, Hubei, China

Bibliografia

• [1] Păun G. Computing with membranes. Journal of Computer and System Sciences, 2000. 61(1):108-143. URL https://doi.org/10.1006/jcss.1999.1693.
• [2] Dassow J, Păun G. On the power of membrane computing. Journal of Universal computer science, 1999. 5(2):33-49. doi:10.3217/jucs-005-02-0033.
• [3] Gheorghe M, Păun G, Pérez-Jiménez MJ. Research frontiers of membrane computing: open problems and research topics. International Journal of Foundations of Computer Science, 2013. 24(5):547-623. URL https://doi.org/10.1142/S0129054113500202.
• [4] Martin-Vide C, Pazos J, Păun G, 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 G, Yokomori T. Spiking neural P systems. Fundamenta Informaticae, 2006. 71(2-3):279-308. URL http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=23094593&lang=zh-cn&site=ehost-live.
• [6] Păun G, Păun R. Membrane computing and economics: numerical P systems. Fundamenta Informaticae, 2006. 72(1-2):213-227. URL http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=22328435&lang=zh-cn&site=ehost-live.
• [7] Zhang X, Pan L, 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.
• [8] Song T, Pan L. 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.
• [9] Leporati A, Manzoni L, Mauri G, Porreca A, Zandron C. Shallow non-confluent P systems. In: Proceedings of the 17th International Conference on Membrane Computing. Springer, 2016 pp. 307-316. doi:10.1007/978-3-319-54072-619.
• [10] Păun A, Păun G. The power of communication: P systems with symport/antiport. New Generation Computing, 2002. 20(3):295-305. URL https://doi.org/10.1007/BF03037362.
• [11] Díaz-Pernil D, Gutierrez-Naranjo MA, Pérez-Jiménez MJ. Solving the independent set problem by using tissue-like P systems with cell division. In: Methods and Models in Artificial and Natural Computation. A Homage to Professor Mira’s Scientific Legacy. 2009 pp. 213-222. doi:10.1007/978-3-642-02264-723.
• [12] Zandron C, Leporati A, Ferretti C. On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. Fundamenta Informaticae, 2008. 87(1):79-91. URL http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=35683155&lang=zh-cn&site=ehost-live.
• [13] Song T, Pan L. Spiking neural P systems with request rules. Neurocomputing, 2016. 193:193-200. doi:10.1016/j.neucom.2016.02.023.
• [14] Zhang G, Gheorghe M, Pérez-Jiménez MJ. Real-life Applications with Membrane Computing. Springer, Berlin, Germany, 2017. ISBN 10:3319559877, 13:978-3319559872.
• [15] Ciobanu G, Păun G, Pérez-Jiménez MJ. Applications of Membrane Computing. Springer-Verlag, Berlin, 2006. doi:10.1007/3-540-29937-8.
• [16] Peng H, Wang J, Pérez-Jiménez MJ, nez ARN. An unsupervised learning algorithm for membrane computing. Information Science, 2015. 304:80-91. URL https://doi.org/10.1016/j.ins.2015.01.019.
• [17] Peng H, Wang J, Shi P, Riscos-Núñez A, Pérez-Jiménez MJ. An automatic clustering algorithm inspired by membrane computing. Pattern Recognition Letters, 2015. 68:34-40. URL https://doi.org/10.1016/j.patrec.2015.08.008.
• [18] Wang J, Shi P, Peng H. Membrane computing model for IIR filter design. Information Science, 2016. 329:164-176. URL https://doi.org/10.1016/j.ins.2015.09.011.
• [19] Zhang G, Pérez-Jiménez MJ, Gheorghe M. Data modeling with membrane systems: applications to real ecosystems. Real-life Applications with Membrane Computing, 2017. 25:259-355. URL https://doi.org/10.1007/978-3-319-55989-6_7.
• [20] Păun G, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. ISBN 9780199556670.
• [21] Alhazov A, Rogozhin Y. Towards a characterization of P systems with minimal symport/antiport and two membranes. Lecture Notes in Computer Science, 2006. 436(1):135-153. doi:10.1007/119635169.
• [22] Jiang S, Wang Y, Xu J, Xu F. The Computational Power of Cell-like P Systems with Symport/Antiport Rules and Promoters. Fundamenta Informaticae, 2019. 164:2-3. doi:10.3233/FI-2019-1763.
• [23] 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.
• [24] Song B, Pérez-Jiménez MJ, Păun G, Pan L. Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division. BioSystems, 2015. 130:51-58. URL https://doi.org/10.1016/j.biosystems.2015.03.002.
• [25] Alhazov A, Rogozhin Y. Generating languages by P systems with minimal symport/antiport. Computer Science Journal of Moldova, 2006. 14(42):299-323.
• [26] 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.
• [27] Song T, Pan L. Spiking neural P systems with rules on synapses working in maximum spikes consumption strategy. IEEE transactions on nanobioscience, 2015. 14(1):38-44. doi:10.1109/TNB.2014.2367506.
• [28] Ciobanu G, Pan L, Păun G. P systems with minimal parallelism. Theoretical Computer Science, 2007. 378(1):117-130. URL https://doi.org/10.1016/j.tcs.2007.03.044.
• [29] Frisco P, Govan G. P systems with active membranes operating under minimal parallelism. In: 12th International Conference on Membrane Computing. Springer, 2011 pp. 165-181. doi:10.1007/978-3-642-28024-512.
• [30] Jiang K, Pan L. Spiking neural P systems with anti-spikes working in sequential mode induced by maximum spike number. Neurocomputing, 2016. 171:1674-1683. URL https://doi.org/10.1016/j.neucom.2015.07.100.
• [31] Frisco P, Govan G, Leporati A. Asynchronous P systems with active membranes. Theoretical Computer Science, 2012. 429:74-86. URL https://doi.org/10.1016/j.tcs.2011.12.026.
• [32] Pan L, Wang J, Hoogeboom HJ. Limited asynchronous spiking neural P systems. Fundamenta Informaticae, 2011. 110(1-4):271-293. doi:10.3233/FI-2011-543.
• [33] Song T, Pan L, Păun G. Asynchronous spiking neural P systems with local synchronization. Information Sciences, 2013. 219:197-207. URL https://doi.org/10.1016/j.ins.2012.07.023.
• [34] Pan L, Păun G, 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.
• [35] Song B, Pérez-Jiménez MJ, Păun G, 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.
• [36] Rozenberg G, Salomaa A. Handbook of Formal Languages, volume 1-3. Springer Science & Business Media, 1997. ISBN 3-540-60420-0.
• [37] Păun G. Membrane Computing: An Introduction. Springer Science & Business Media, Berlin, 2002. doi:10.1007/978-3-642-56196-2.
• [38] Korec I. Small universal register machines. Theoretical Computer Science, 1996. 168(2):267-301. URL https://doi.org/10.1016/S0304-3975(96)00080-1.
• [39] Minsky M. Computation: Finite and Infinite Machines. Prentice-Hall, 1967. ISBN 0-13-165563-9.
• [40] Freund R, Ibarra OH, Păun G, Yen HC. Matrix languages, register machines, vector addition systems. In: Proceedings of the 3rd Brainstorming Week Membrane Computing. 2005 pp. 155-168. URL http://hdl.handle.net/11441/36776.
• [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(4):423-434. doi:10.25596/jalc-2006-423.
• [42] Sosík P, Rodríguez-Patón A. Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences, 2007. 73:137-152. URL https://doi.org/10.1016/j.jcss.2006.10.001.
• [43] Pérez-Jiménez MJ. An approach to computational complexity in membrane computing. In: International Workshop on Membrane Computing. Springer, 2004 pp. 85-109. doi:10.1007/978-3-540-31837-85.
• [44] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, 1979. ISBN 0716710447.
• [45] Liu X, Suo J, Leung SCH, Liu J, Zeng X. The power of time-free tissue P systems: attacking NP-complete problems. NeuroComputing, 2015. 159:151-156. URL https://doi.org/10.1016/j.neucom.2015.01.072.
• [46] Song B, Pérez-Jiménez MJ, Pan L. An efficient time-free solution to SAT problem by P systems with proteins on membranes. Journal of Computer and System Sciences, 2016. 82:1090-1099. URL https://doi.org/10.1016/j.jcss.2016.03.008.
• [47] 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. URL https://doi.org/10.1017/S0960129515000018.
• [48] Alhazov A, Freund R, Verlan S. P systems working in set modes. In: Proceedings of the Workshop on Membrane Computing. Manchester, 2016 pp. 4-15.
• [49] Macías-Ramos LF, Song B, Valencia-Cabrera L, Pan L, Pérez-Jiménez MJ. Membrane fission: a computational complexity perspective. Complexity, 2015. 21(6):321-334. doi:10.1002/cplx.21691.
• [50] Sosík P, Luděk C. Computational power of cell separation in tissue P systems. Information Sciences, 2014. 279:805-815. URL https://doi.org/10.1016/j.ins.2014.04.031.
• [51] Valencia-Cabrera L, Song B, Macías-Ramos LF, Pan L, Pérez-Jiménez MJ. Computational efficiency of P systems with symport/antiport rules and membrane separation. In: Proceedings of the 13th Brainstorming Week on Membrane Computing. Sevilla, 2015 pp. 325-370. URL http://hdl.handle.net/11441/33124.
• [52] Pan L, Alhazov A. Solving HPP and SAT by P systems with active membranes and separation rules. Acta Informatica, 2006. 43:131-145. doi:10.1007/s00236-006-0018-8.
• [53] Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F. Complexity classes in models of cellular computing with membranes. Natural Computing, 2003. 2(3):265-285. doi:10.1023/A:1025449224520.
• [54] Pérez-Jiménez MJ. A computational complexity theory in membrane computing. In: 10th International Workshop on Membrane Computing. Springer, 2009 pp. 82-105. doi:10.1007/978-3-642-11467-010.
• [55] Csuhaj-Varjú E, Margenstern M, Vaszil G, Verlan S. On small universal antiport P systems. Theoretical Computer Science, 2007. 372:152-164. URL https://doi.org/10.1016/j.tcs.2006.11.023.
• [56] Adorna H, Păun G, Pérez-Jiménez MJ. On communication complexity in evolution communication P systems. Information Science and Technology, 2010. 13(2):113-130. URL http://www.imt.ro/romjist/Volum13/Number13_2/abstracts.htm#2.

Uwagi

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