Membrane Creation in Polarizationless P Systems with Active Membranes

• Autorzy: Orellana-Martín, David , Valencia-Cabrera, Luis , Riscos-Núñez, Agustín , Pérez-Jiménez, Mario J.
• Języki publikacji: EN

Abstrakty

EN

Biological membranes play an active role in the evolution of cells over time. In the framework of Membrane Computing, P systems with active membranes capture this idea, and the possibility to increase the number of membranes during a computation. Classically, it has been considered, by using division rules, inspired in the mitosis process. Initially, the membranes in these models are supposed to have an electrical polarization (positive, negative or neutral) and the semantics is minimalist, in the sense that rules are applied in parallel, but in one transition step, each membrane can be the subject of at most one rule of types communication, dissolution or division. This paper focuses on polarizationless P systems with active membranes in which membrane creation rules are considered instead of membrane division rules as a mechanism to construct an exponential workspace, expressed both in terms of number of objects and membranes, in linear time. Moreover, the minimalist semantics is considered and some complexity results are provided in this framework, allowing to tackle the P versus NP problem from a new perspective. An original frontier of the efficiency in this context is unveiled in this paper: allowing membrane creation rules to be applicable in any membrane of the system, instead of restricting them to only elementary membranes, yields a significant boost on the computational power. More precisely, only problems in P can be efficiently solved in the restricted case, while in the non-restricted case an efficient and uniform solution to a PSPACE-complete problem is provided.

Słowa kluczowe

EN

biological membranes; cellular evolution; creation; semantics

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 297--311
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Orellana-Martín, David

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Sevilla, Spain,

autor

Valencia-Cabrera, Luis

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Sevilla, Spain,

autor

Riscos-Núñez, Agustín

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Sevilla, Spain,

autor

Pérez-Jiménez, Mario J.

• Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Sevilla, Spain,

Bibliografia

• [1] Alhazov A, Ishdorj T-O. Membrane operations in P systems with active membranes. In Gh. Păun, A. Riscos-Núñez, A. Romero-Jiménez, F. Sancho-Caparrini (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, Sevilla, 2004 pp. 37-44. URI http://hdl.handle.net/11441/34550.
• [2] Arroyo F, Baranda AV, Castellanos J, Păun Gh. Membrane computing, The power of (rule) creation, JUCS, 2002. 8(3):369-381. doi:10.3217/jucs-008-03-0369.
• [3] Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Romero-Campero FJ. A linear solution of Subset Sum problem by using membrane creation. Lecture Notes in Computer Science, 2005. 3561:258-267. doi:10.1007/11499220_27.
• [4] Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A, Romero-Campero FJ, Romero-Jiménez A. Characterizing tractability by cell-like membrane systems. In K.G. Subramanian, K. Rangarajan, M. Mukund (eds.) Formal models, languages and applications, World Scientific, Singapore, 2006 pp. 137-154. doi:10.1142/9789812773036_0009.
• [5] Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Romero-Campero FJ. A linear time solution for QSAT with membrane creation. Vol. 3850 Lecture Notes in Computer Science, 2006. 3850:241-252. doi:10.1007/11603047_17.
• [6] Martín-Vide C, Păun Gh, Rodríguez-Patón A. On P Systems with Membrane Creation. Computer Science Journal of Moldova, 2001. 9(2):134-145.
• [7] Martín-Vide C, Păun Gh, Pazos J, Rodríguez-Patón A. A New Class of Symbolic Abstract Neural Nets: Tissue P Systems. Computing and Combinatorics, 8th Annual International Conference, COCOON 2002 Singapore, August 15-17, 2002, Proceedings. Vol. 2387 Lecture Notes in Computer Science, 2002. 2387:290-299. doi:10.1007/3-540-45655-4_32.
• [8] Martín-Vide C, Păun Gh, Pazos J, Rodríguez-Patón A. Tissue P Systems. Theoretical Computer Science, 2003. 296(2):295-326. doi:10.1016/S0304-3975(02)00659-X.
• [9] Mutyam M, Krithivasan K. P systems with membrane creation: Universality and efficiency. Vol. 2055 Lecture Notes in Computer Science, 2001. 2055:276-287. doi:10.1007/3-540-45132-3_19.
• [10] Orellana-Martín D, Valencia-Cabrera L, Song B, Pan L, Pérez-Jiménez MJ. Narrowing frontiers with evolutional communication rules and cell separation. In D. Orellana-Martín, Gh. Paun, A. Riscos-Núñez, L. Valencia-Cabrera (eds.) Proceedings of the Sixteenth Brainstorming Week on Membrane Computing, January 30, Sevilla, Spain, 2018 pp. 139-161. URI https://hdl.handle.net/11441/84116.
• [11] Orellana-Martín D, Valencia-Cabrera L, Riscos-Núñez A, Pérez-Jiménez MJ. A semantic frontier of efficiency in membrane systems. Preliminary Proceedings of the Seventh Asian Conference on Membrane Computing (ACMC2018), University of Auckland, Auckland, New Zealand, December 10-13, 2018.
• [12] Pan L, Ishdorj T-O. P systems with active membranes and separation rules. Journal of Universal Computer Science, 2004. 10(5):630-649. URI http://hdl.handle.net/11441/36345.
• [13] 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, Article ID:3745210. doi:10.1155/2018/3745210.
• [14] Papadimitriou CH, Computational Complexity, Addison-Wesley. 1995.
• [15] Păun A, Păun M. On the Membrane Computing based on splicing. In C. Martín-Vide, V. Mitrana (eds.) Where Mathematics, Computer Science, Linguistics and Biology Meet: Essays in honour of Gheorghe Păun, Kluwer, 2001 pp. 409-422. doi:10.1007/978-94-015-9634-3_36.
• [16] 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.
• [17] Păun Gh. Computing with membranes. Journal of Computer and System Sciences, 2000. 61(1):108-143, and Turku Center for CS-TUCS Report No. 208, 1998. doi:10.1006/jcss.1999.1693.
• [18] Păun Gh. P systems with active membranes: attacking NP-complete problems, Journal of Automata, Languages and Combinatorics, 2001. 6(1):75-90.
• [19] Păun Gh, Sakakibara Y, Yokomori T. P systems on graphs of restricted forms. Publicationes Mathematicae, 2002. 60(3):217-231.
• [20] Păun Gh, Yokomori T. Membrane Computing based on splicing. In E. Winfree, D.K. Guidford (eds.) DNA based Computers V. DIMACS, Series Discrete Mathematics Theoretical Computer Science, 1999. 54:217-231.
• [21] Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F. Complexity classes in cellular computing with membranes. Natural Computing, 2003. 2(3):265-285. doi:10.1023/A:1025449224520.
• [22] Song B, Pérez-Jiménez MJ, Pan L. Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division, BioSystems, 2015. 130:51-58. doi:10.1016/j.biosystems.2015.03.002.
• [23] Song B, Zhang C, Pan L. Tissue-like P systems with evolutional symport/antiport rules, Information Sciences, 2017. 378:177-193. doi:10.1016/j.ins.2016.10.046.
• [24] Romero-Jiménez Á, Orellana-Martín D. Design Patterns for Efficient Solutions to NP-Complete Problems in Membrane Computing. In: Graciani C., Riscos-Núñez A., Păun G., Rozenberg G., Salomaa A. (eds) Enjoying Natural Computing. Vol. 11270 Lecture Notes in Computer Science, 2018. 11270:237-255. doi:10.1007/978-3-030-00265-7_19.
• [25] P systems web page. http://ppage.psystems.eu/.
• [26] Bulletin of the Int. MC Society. http://membranecomputing.net/IMCSBulletin/.

Uwagi

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

Identyfikatory

DOI

10.3233/FI-2020-1884