Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems. (English) Zbl 1431.68034
Summary: Cooperation is doubtless a relevant ingredient on rewriting rules based computing models. This paper provides an overview on both classical and newest results studying how cooperation among objects influences the ability of cell-like membrane systems to solve computationally hard problems in an efficient way. In this paper, two types of such membrane systems will be considered: (a) polarizationless P systems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules; and (b) cell-like P systems with symport/antiport rules of minimal length. Specifically, assuming that P is not equal to NP, several frontiers of the efficiency are obtained in these two computing frameworks, in such manner that each borderline provides a tool to tackle the P versus NP problem.
MSC:
| 68Q07 | Biologically inspired models of computation (DNA computing, membrane computing, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Alhazov A, Pérez-Jiménez MJ. Uniform solution of QSAT using polarizationless active membranes. In Durand-Lose J, Margenstern M, editors. Machines, computations, and universality. Lecture notes in computer science, vol. 4664; 2007. pp. 122-33. · Zbl 1211.68194 |
| [2] | Pavel AB, Buiu C. Using enzymatic numerical P systems for modeling mobile robot controllers. Nat Comput. 2012;11(3):387-93. · Zbl 1251.68104 · doi:10.1007/s11047-011-9286-5 |
| [3] | Celiker H, Gore J. Cellular cooperation: insights from microbes. Trends Cell Biol Trends Cell Biol. 2013;23(1):9-15. · doi:10.1016/j.tcb.2012.08.010 |
| [4] | Freund R, Păun Gh. On the number of non-terminal symbols in graph-controlled, programmed and matrix grammars. In Margenstern M, Rogozhin Y, editors. Machines, computations, and universality, international conference on machines, computations, and universality. Berlin, Heidelberg: Springer; 2001. pp. 214-25. · Zbl 0984.68091 |
| [5] | Frisco P, Gheorghe M, Pérez-Jiménez MJ. Applications of membrane computing in systems and synthetic biology. Complexity and computation series: emergence. 2014. |
| [6] | García-Quismondo M, Graciani C, Riscos-Núñez A. Membrane computing as a modelling tool: looking back and forward from Sevilla. In Graciani C, Riscos-Núñez A, Păun Gh, Rozenberg Gr, Salomaa A, editors. Enjoying natural computing: essays dedicated to Mario de Jesús Pérez-Jiménez on the occasion of his 70th birthday. Springer International Publishing; 2018. pp. 114-29. · Zbl 1519.68088 |
| [7] | Garey MR, Johnson DS. Computers and intractability a guide to the theory of NP-completeness. Freeman and Company; 1979. · Zbl 0411.68039 |
| [8] | Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A, Romero-Campero FJ. On the power of dissolution in P systems with active membranes. In Freund R, Păun Gh, Rozenberg Gr, Salomaa A, editors. Membrane computing, 6th international workshop, WMC 2005, Vienna, Austria, July 18-21, 2005. Revised Selected and Invited Papers. Lecture notes in computer science, vol. 3850; 2006. pp. 224-40. · Zbl 1135.68410 |
| [9] | Leporati A, Ferretti C, Mauri G, Pérez-Jiménez MJ, Zandron C. Complexity aspects of polarizationless membrane systems. Nat Comput. 2009;8(4):703-17. · Zbl 1185.68339 · doi:10.1007/s11047-008-9100-1 |
| [10] | 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(6):321-34. · doi:10.1002/cplx.21691 |
| [11] | Papadimitriou CH. Computational complexity. Boston: Addison-Wesley Publishing Company; 1994. · Zbl 0833.68049 |
| [12] | Pan L, Păun Gh, Pérez-Jiménez MJ, Song T. Bio-inspired Computing: theories and applications. Communications in computer and information science series; 2014. |
| [13] | Păun A, Păun Gh. The power of communication: P systems with symport/antiport. N Gener Comput. 2002;20(3):295-305. · Zbl 1024.68037 · doi:10.1007/BF03037362 |
| [14] | Păun Gh, Rozenberg G, Salomaa A. The Oxford handbook of membrane computing. Oxford: Oxford University Press; 2009. · Zbl 1237.68001 |
| [15] | Păun Gh. Computing with membranes. J Comput Syst Sci. 2000;61(1):108-43. · Zbl 0956.68055 · doi:10.1006/jcss.1999.1693 |
| [16] | Păun, Gh; Ibarra, OH (ed.); Dang, Z. (ed.), Languages in membrane computing: some details for spiking neural P systems, 20-35 (2006), Berlin, Heidelberg · Zbl 1227.68067 · doi:10.1007/11779148_3 |
| [17] | Păun Gh. Membrane computing: an introduction. New York: Springer Natural Computing Series; 2002. · Zbl 1034.68037 · doi:10.1007/978-3-642-56196-2 |
| [18] | Păun Gh. P systems with active membranes: attacking NP-complete problems. J Autom Lang Comb. 2001;6:75-90. · Zbl 0970.68066 |
| [19] | Pérez-Jiménez MJ, Romero-Jiménez Á, Sancho-Caparrini F. Complexity classes in models of cellular computing with membranes. Nat Comput. 2003;2(3):265-85. https://doi.org/10.1023/A:1025449224520. · Zbl 1048.68043 · doi:10.1023/A:1025449224520 |
| [20] | 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-8. · doi:10.1016/j.biosystems.2015.03.002 |
| [21] | Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, Pérez-Jiménez MJ, Riscos-Núñez A. Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes. Fundam Inf. 2017;153(1-2):147-72. · Zbl 1377.68088 · doi:10.3233/FI-2017-1535 |
| [22] | Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, Pérez-Jiménez MJ, Riscos-Núñez A. Polarizationless P systems with active membranes: Computational complexity aspects. J Autom Lang Comb. 2016;21(1-2):107-23. · Zbl 1356.68071 |
| [23] | Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez-Jiménez MJ. Counting membrane systems. In: Proceedings of the Eighteenth International Conference on Membrane Computing (CMC18), July 24-28, 2017. Bradford; 2017. pp. 359-72. · Zbl 1497.68205 |
| [24] | Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez-Jiménez MJ. Minimal cooperation in polarizationless P systems with active membranes. In Graciani C, Păun Gh, Orellana-Martín D, Riscos-Núñez A, Valencia-Cabrera L, editors. Proceedings of the Fourteenth Brainstorming Week on Membrane Computing, 1-5 February, 2016. Sevilla; 2016. pp. 327-56. · Zbl 1356.68071 |
| [25] | Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez-Jiménez MJ. Reaching efficiency through complicity in membrane systems: dissolution, polarization and cooperation. Theor Comput Sci. 2017;701:226-34. · Zbl 1382.68079 · doi:10.1016/j.tcs.2017.04.015 |
| [26] | Valencia-Cabrera L, Song B, Macías-Ramos LF, Pan L, Riscos-Núñez A, Pérez-Jiménez MJ. Minimal cooperation in P systems with symport/antiport: a complexity approach. In Macías LF, Păun Gh, Riscos A, Valencia L, editors. Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 2-6 February, 2015. Sevilla; 2015. pp. 301-23. |
| [27] | Wang T, Zhang GX, Pérez-Jiménez MJ. Fuzzy membrane computing: theory and applications. Int J Comput Commun Control. 2015;10(6):904-35. |
| [28] | Zandron, C.; Ferretti, C.; Mauri, G.; Antoniou, I. (ed.); Calude, CS (ed.); Dinneen, MJ (ed.), Solving NPcomplete problems using P systems with active membranes, 289-301 (2000), Heidelberg · Zbl 0967.68074 |
| [29] | Zhang G, Pérez-Jiménez MJ, Gheorghe M. Real-life applications with Membrane Computing. Complexity and computation series: emergence; 2017. · Zbl 1387.68005 |
| [30] | http://ppage.psystems.eu/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
