P systems attacking hard problems beyond NP: a survey

Alhazov, A., Freund, R., Oswald, M. (2005). Tissue P systems with antiport rules and small numbers of symbols and cells. In: C. De Felice, A. Restivo (Eds.) Developments in Language Theory, DLT 2005, Lecture Notes in Computer Science (vol. 3572, pp. 54–78). Berlin: Springer

Alhazov, A., Leporati, A., Mauri, G., Porreca, A. E., & Zandron, C. (2014). Space complexity equivalence of P systems with active membranes and turing machines. Theoretical Computer Science, 529, 69–81.

Alhazov, A., Martín-Vide, C., & Pan, L. (2003). Solving a PSPACE-complete problem by P systems with restricted active membranes. Fundamenta Informaticae, 58(2), 67–77.

Alhazov, A., & Pérez-Jiménez, M. (2007). Uniform solution of QSAT using polarizationless active membranes. In: J. Durand-Lose, M. Margenstern (Eds.) Machines, Computations, and Universality, 5th International Conference, MCU 2007, Lecture Notes in Computer Science (vol. 4664, pp. 122–133). Springer.

Bernardini, F., & Gheorghe, M. (2005). Cell communication in tissue P systems and cell division in population P systems. Soft Computing, 9(9), 640–649.

Cavaliere, M. (2013). Time-free solutions to hard computational problems. In: M. Gheorghe, G. Păun, M.J. Pérez-Jiménez, G. Rozenberg (Eds.) Research Frontiers of Membrane Computing: Open Problems and Research Topics, International Journal of Foundations of Computer Science (vol. 24 (5), pp. 579–582). World Scientific (2013). Section 11

Cavaliere, M., & Sburlan, D. (2005). Time-independent P systems. In: G. Mauri, G. Paun, M.J. Pérez-Jiménez, G. Rozenberg, A. Salomaa (Eds.) Membrane Computing, 5th International Workshop, WMC 2004, Lecture Notes in Computer Science (vol. 3365, pp. 239–258). Springer

Chandra, A.K., & Stockmeyer, L.J. (1976). Alternation. In: 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25–27 October 1976, pp. 98–108. IEEE Computer Society. https://doi.org/10.1109/SFCS.1976.4

Csuhaj-Varjú, E., Gheorghe, M., Rozenberg, G., Salomaa, A., & Vaszil, G. (Eds.). (2013). Membrane Computing—13th International Conference, CMC13, Lecture Notes in Computer Science (vol. 7762). Springer

Díaz-Pernil, D., Pérez-Jiménez, M. J., & Romero-Jiménez, Á. (2009). Efficient simulation of tissue-like P systems by transition cell-like P systems. Natural Computing, 8(4), 797–806.

Eleftherakis, G., Kefalas, P., Paun, G., Rozenberg, G., & Salomaa, A. (eds.) (2007). Membrane Computing, 8th International Workshop, WMC 2007, Lecture Notes in Computer Science (vol. 4860). Springer

Freund, R., Păun, G., & Pérez-Jiménez, M. (2005). Tissue P systems with channel states. Theoretical Computer Science, 330, 101–116.

Gutiérrez-Escudero, R., Pérez-Jiménez, M., & Rius-Font, M. Characterizing tractability by tissue-like P systems. In: Păun et al. [53], pp. 289–300

Ionescu, M., Păun, G., & Yokomori, T. (2006). Spiking neural P systems. Fundamenta Informaticae, 71(2—-3), 279–308.

Ishdorj, T. O., Leporati, A., Pan, L., Zeng, X., & Zhang, X. (2010). Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theoretical Computer Science, 411(25), 2345–2358.

Krishna, S., Lakshmanan, K., & Rama, R. (2003). Tissue P systems with contextual and rewriting rules. In: Paun, G., Rozenberg, G., Salomaa, A., Zandron C. (Eds.) Membrane Computing, Lecture Notes in Computer Science (vol. 2597, pp. 339–351). Springer, Berlin

Krishna, S.N. (2007). On the computational power of flip-flop proteins on membranes. In: S.B. Cooper, B. Löwe, A. Sorbi (Eds.) Computation and Logic in the Real World, Lecture Notes in Computer Science (vol. 4497, pp. 695–704). Springer

Lakshmanan, K., & Rama, R. (2006). The computational efficiency of insertion-deletion tissue P systems. In K. Subramanian, K. Rangarajan, & M. Mukund (Eds.), Formal Models, Languages and Applications (pp. 235–245). New York: World Scientific.

van Leeuwen, J. (Ed.). (1990). Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity. Amsterdam: Elsevier.

Leporati, A. (2014). Computational complexity of P systems with active membranes. In: A. Alhazov, S. Cojocaru, M. Gheorghe, Y. Rogozhin, G. Rozenberg, A. Salomaa (Eds.) Fourteenth International Conference on Membrane Computing, CMC14, Lecture Notes in Computer Science (vol. 8340). Berlin: Springer.

Leporati, A., Ferretti, C., Mauri, G., Pérez-Jiménez, M., & Zandron, C. (2009). Complexity aspects of polarizationless membrane systems. Natural Computing, 8(4), 703–717.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2014). Simulating elementary active membranes, with an application to the P conjecture. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sosík, C. Zandron (Eds.) Membrane Computing—15th International Conference, CMC15, Lecture Notes in Computer Science (vol. 8961, pp. 284–299). Springer.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2015). Membrane division, oracles, and the counting hierarchy. Fundamental Information, 138(1–2), 97–111.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2017). Characterising the complexity of tissue P systems with fission rules. Journal of Computer and System Sciences, 90, 115–128.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2017). Shallow non-confluent P systems. In: A. Leporati, G. Rozenberg, A. Salomaa, C. Zandron (Eds.) Membrane Computing: 17th International Conference, CMC 2016, Lecture Notes in Computer Science (vol. 10105, pp. 307–316). Cham: Springer

Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2018) Solving qsat in sublinear depth. In: T. Hinze, J. Behre (Eds.) Proceedings of the Nineteenth International Conference on Membrane Computing (CMC19) (pp. 149–162). Berlin: Pro Business.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2018). Subroutines in P systems and closure properties of their complexity classes. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2018.06.012 .

Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2018). A survey on space complexity of P systems with active membranes. International Journal of Advances in Engineering Sciences and Applied Mathematics, 10(3), 221–229.

Leporati, A., Zandron, C., Ferretti, C., & Mauri, G. (2007). On the computational power of spiking neural P systems. In M. Gutiérrez-Naranjo, G. Păun, A. Romero-Jiménez, & A. Riscos-Núnez (Eds.), Fifth Brainstorming Week on Membrane Computing (pp. 227–245). Sevilla: Fenix Editora.

Liu, X., Suo, J., Leung, S., Liu, J., & Zeng, X. (2015). The power of time-free tissue P systems: Attacking NP-complete problems. Neurocomputing, 159(1), 151–156.

Macías-Ramos, L.F., Pérez-Jiménez, M.J., Riscos-Núñez, A., Rius-Font, M., & Valencia-Cabrera, L. The efficiency of tissue P systems with cell separation relies on the environment. In: Csuhaj-Varjú et al. [9] (pp. 243–256).

Martín Vide, C., Pazos, J., Păun, G., & Rodríguez Patón, A. (2002). A new class of symbolic abstract neural nets: Tissue P systems. In: O. Ibarra, L. Zhang (Eds.) Computing and Combinatorics, Lecture Notes in Computer Science (vol. 2387, pp. 573–679). Berlin: Springer.

Martín Vide, C., Pazos, J., Păun, G., & Rodríguez Patón, A. (2003). Tissue P systems. Theoretical Computer Science, 296, 295–326.

Mauri, G., Leporati, A., Manzoni, L., Porreca, A.E., & Zandron, C. (2015). Complexity classes for membrane systems: A survey. In: A.H. Dediu, E. Formenti, C. Martín-Vide, B. Truthe (Eds.) Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Lecture Notes in Computer Science (vol. 8977, pp. 56–69). Springer.

Murphy, N., & Woods, D. Active membrane systems without charges and using only symmetric elementary division characterise P. In: Eleftherakis et al. [11] (pp. 367–384).

Murphy, N., & Woods, D. (2011). The computational power of membrane systems under tight uniformity conditions. Natural Computing, 10(1), 613–632.

Murphy, N., & Woods, D. (2014). Uniformity is weaker than semi-uniformity for some membrane systems. Fundamenta Informaticae, 134(1–2), 129–152.

Orellana-Martín, D., Martínez-del Amor, M. Á., Pérez-Hurtado, I., Riscos-Núñez, A., Valencia-Cabrera, L., & Pérez-Jiménez, M. J. (2018). When object production tunes the efficiency of membrane systems. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2018.04.013 .

Pan, L., & Ishdorj, T. O. (2004). P systems with active membranes and separation rules. Journal of Universal Computer Science, 10(5), 630–649.

Pan, L., Păun, G., & Pérez-Jiménez, M. J. (2011). Spiking neural P systems with neuron division and budding. Science China Information Sciences, 54(8), 1596.

Pan, L., Song, B., Valencia-Cabrera, L., & Pérez-Jiménez, M. J. (2018). The computational complexity of tissue P systems with evolutional symport/antiport rules. Complexity. https://doi.org/10.1155/2018/3745210 .

Păun, A., & Rodríguez-Patón, A. On flip-flop membrane systems with proteins. In: Eleftherakis et al. [11]. (pp. 414–427).

Pérez-Jiménez, M. A computational complexity theory in membrane computing. In: Păun et al. [53] (pp. 125–148).

Pérez-Jiménez, M., Romero-Jiménez, A., & Sancho-Caparrini, F. (2003). Complexity classes in models of cellular computing with membranes. Natural Computing, 2, 265–285.

Pérez-Jiménez, M. J., & Sosík, P. (2015). An optimal frontier of the efficiency of tissue P systems with cell separation. Fundamental Information, 138(1–2), 45–60.

Porreca, A., Leporati, A., Mauri, G., & Zandron, C. (2011). P systems with elementary active membranes: beyond NP and coNP. In: M. Gheorghe, T. Hinze, G. Păun, G. Rozenberg, A. Salomaa (eds.) Membrane Computing—11th International Conference, CMC11, Lecture Notes in Computer Science (vol. 6501, pp. 383–392). Springer.

Porreca, A.E., Leporati, A., Mauri, G., & Zandron, C. (2012). P systems simulating oracle computations. In: M. Gheorghe, G. Păun, G. Rozenberg, A. Salomaa, S. Verlan (eds.) Membrane Computing—12th International Conference, CMC12, Lecture Notes in Computer Science (vol. 7184, pp. 346–358). Springer.

Porreca, A. E., Mauri, G., & Zandron, C. (2010). Non-confluence in divisionless P systems with active membranes. Theoretical Computer Science, 411(6), 878–887.

Porreca, A.E., Murphy, N., & Pérez-Jiménez, M.J. (2012). An optimal frontier of the efficiency of tissue P systems with cell division. In: García-Quismondo, M. et al. (ed.) Proceedings of the Tenth Brainstorming Week on Membrane Computing (vol. II, pp. 141–166). Fénix Editora, Sevilla.

Păun, A., & Popa, B. (2006). P systems with proteins on membranes. Fundamenta Informaticae, 72(4), 467–483.

Păun, A., & Popa, B. (2006) P systems with proteins on membranes and membrane division. In: O. Ibarra, Z. Dang (Eds.) Developments in Language Theory, DLT 2006, Lecture Notes in Computer Science (vol. 4036, pp. 292–303). Berlin: Springer.

Păun, A., & Păun, G. (2002). The power of communication: P systems with symport/antiport. New Generation Computer, 20(3), 295–306.

Păun, G., Pérez-Jiménez, M., Riscos-Núnez, A., Rozenberg, G., & Salomaa, A. (eds.) (2010). Membrane Computing, 10th International Workshop, WMC 2009, Lecture Notes in Computer Science (vol. 5957). Berlin: Springer.

Păun, G., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford Handbook of Membrane Computing. Oxford: Oxford University Press.

Păun, G. (2001). P systems with active membranes: attacking NP-complete problems. Journal of Automata, Languages, and Combinatorics, 6(1), 75–90.

Song, B., Pérez-Jiménez, M. J., & Pan, L. (2015). Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division. Biosystems, 130, 51–58.

Song, B., Pérez-Jiménez, M. J., & Pan, L. (2017). An efficient time-free solution to QSAT problem using P systems with proteins on membranes. Information and Computation, 256, 287–299.

Song, B., Song, T., & Pan, L. (2017). A time-free uniform solution to subset sum problem by tissue P systems with cell division. Mathematical Structures in Computer Science, 27(1), 17–32.

Song, T., Macas-Ramos, L. F., Pan, L., & Pérez-Jiménez, M. J. (2014). Time-free solution to SAT problem using P systems with active membranes. Theoretical Computer Science, 529, 61–68.

Sosík, P. Limits of the power of tissue P systems with cell division. In: Csuhaj-Varjú et al. [9] (pp. 390–403).

Sosík, P., & Cienciala, L. (2012). Tissue P systems with cell separation: upper bound by PSPACE. In: A.H. Dediu, C. Martín-Vide, B. Truthe (Eds.) Theory and Practice of Natural Computing, TPNC 2012, Lecture Notes in Computer Science (vol. 7505, pp. 201–215). Springer.

Sosík, P., & Rodríguez-Patón, A. (2007). Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences, 73(1), 137–152.

Sosík, P. (2011). Selected topics in computational complexity of membrane systems. In: J. Kelemen, A. Kelemenová (Eds.) Computation, Cooperation and Life, Lecture Notes in Computer Science (vol. 6610, pp. 125–137). Springer.

Sosík, P., Păun, A., & Rodríguez-Patón, A. (2013). P systems with proteins on membranes characterize pspace. Theoretical Computer Science, 488, 78–95.

Sosík, P., Rodríguez-Patón, A., & Ciencialová, L. (2013). Polynomial time bounded computations in spiking neural P systems. Neural Network World, 23(1), 31–48. IF=0,412.

Valsecchi, A., Porreca, A., Leporati, A., Mauri, G., & Zandron, C. An efficient simulation of polynomial-space turing machines by P systems with active membranes. In: Păun et al. [53] (pp. 461–478).

Zandron, C., Leporati, A., Ferretti, C., Mauri, G., & Pérez-Jiménez, M. (2008). On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. Fundamenta Informaticae, 87(1), 79–91.