Bounding the space in P systems with active membranes

Alhazov, A., Martin-Vide, C., & Pan, L. (2003). Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes. Fundamenta Informaticae, 58(2), 67–77. 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., Pan, L., & Păun, Gh. (2004). Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41, 111–144. Gazdag, Z., & Kolonits, G. (2019). A new method to simulate restricted variants of polarizationless P systems with active membranes. Journal of Membrane Computing, 1(4), 251–261. https://doi.org/10.1007/s41965-019-00024-z. Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A., & Romero-Campero, F. J. (2006). On the power of dissolution in P systems with active membranes, In: Freund, R., Păun, G., Rozenberg, Salomaa, A., (eds), 6th International Workshop on Membrane Computing, WMC 2005, LNCS 3850, Springer, 224–240. Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., & Romero-Campero, F. J. (2006). A Linear Solution for QSAT with Membrane Creation. In R. Freund, Gh Păun, G. Rozenberg, & A. Salomaa (Eds.), 6th International Workshop on Membrane Computing (pp. 241–252). WMC 2005, LNCS 3850, Springer, New York. Ishdorj, T. O., Replicative, Ionescu M., Rules, Distribution, & in P Systems with Active Membranes, ICTAC. (2004). LNCS 3407. Springer, New York, 2004, 68–83. Leporati, A., Ferretti, C., Mauri, G., Pérez-Jiménez, M. J., & Zandron, C. (2008). Complexity aspects of polarizationless membrane systems. Natural Computing, 8(4), 703–717. Leporati, A., Mauri, G., Porreca, A. E., & Zandron, C. (2011). Elementary active membranes have the power of counting. International Journal of Natural Computing Research, 2(3), 35–48. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2014). A gap in the space hierarchy of P systems with active membranes. Journal of Automata, Languages and Combinatorics, 19(1–4), 173–184. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2014). Constant-space P systems with active membranes. Fundamenta Informaticae, 134, 111–128. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2014). Simulating Elementary Active Membrane. In M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sosík, & C. Zandron (Eds.), 15th International Conference on Membrane Computing (pp. 284–299). CMC 2014, LNCS 8961, Springer, New York. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2015). Membrane division, oracles, and the counting hierarchy. Fundamenta Informaticae, 138, 97–111. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2016). Monodirectional P systems. Natural Computing, 15, 551–564. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2017). A toolbox for simpler active membrane algorithms. Theoretical Computer Science, 673, 42–57. 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. (2016). Shallow non-confluent P systems. In A. Leporati, G. Rozenberg, A. Salomaa, & C. Zandron (Eds.), 17th International Conference on Membrane Computing (pp. 307–316). CMC 2016, LNCS 10105, Springer, New York. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2018). Solving QSAT in sublinear depth. In T. Hinze, G. Rozenberg, A. Salomaa, & C. Zandron (Eds.), 19th International Conference on Membrane Computing (pp. 188–201). CMC 2018, LNCS 11399, Springer, New York. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2019). Characterizing PSPACE with shallow non-confluent P systems. Journal of Membrane Computing, 1(2), 75–84. https://doi.org/10.1007/s41965-019-00011-4. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2020). Shallow laconic P systems can count. Journal of Membrane Computing, 1(1), 49–58. https://doi.org/10.1007/s41965-020-00032-4. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2020). A Turing machine simulation by P systems without charges. Journal of Membrane Computing,. https://doi.org/10.1007/s41965-020-00031-5. Mauri, G., Pérez-Jiménez, M. J., Zandron, C., & On a Păun’s conjecture in membrane systems, IWINAC,. (2007). LNCS 4527. Springer, New York, 2007, 180–192. Mix Barrington, D. A., Immerman, N., & Straubing, H. (1990). On uniformity within \(\rm NC^1\). Journal of Computer and System Sciences, 41(3), 274–306. Murphy, N., Woods, D., & Active membrane systems without charges and using only symmetric elementary division characterise P, 8th Workshop on Membrane Computing, WMC, (2007). LNCS 4860. Springer, New York, 2007, 367–384. Murphy, N., & Woods, D. (2011). The computational power of membrane systems under tight uniformity conditions. Natural Computing, 10(1), 613–632. Orellana-Martín, D., Valencia-Cabrera, L., Riscos-Núñez, A., & Pérez-Jiménez, M. J. (2019). Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems. Journal of Membrane Computing, 1(2), 85–92. https://doi.org/10.1007/s41965-018-00004-9. Papadimitriou, C. H. (1993). Computational Complexity. Boston: Addison-Wesley. Păun, Gh. (2001). P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics, 6(1), 75–90. Păun, Gh, Rozenberg, G., & Salomaa, A. (Eds.). (2010). Handbook of Membrane Computing. Oxford: Oxford University Press. Pérez-Jiménez, M. J. (2009). A Computational Complexity Theory in Membrane Computing. In Gh Păun, M. J. Pérez-Jiménez, A. Riscos-Núñez, G. Rozenberg, & A. Salomaa (Eds.), Tenth International Workshop on Membrane Computing (pp. 125–148). WMC 2009, LNCS 5957, Springer, New York. Pérez-Jiménez, M. J., & Riscos-Núñez, A. (2005). Solving the subset-sum problem by P systems with active membranes. New Generation Computing, 23, 339–356. Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Jiménez, A., & Woods, D. (2010). Complexity - Membrane division, membrane creation. In Gh Păun, G. Rozenberg, & A. Salomaa (Eds.), Handbook of Membrane Computing (Vol. 12, pp. 302–336). Oxford: Oxford University Press. Porreca, A. E., Leporati, A., Mauri, G., & Zandron, C. (2009). Introducing a space complexity measure for P systems. International Journal of Computing, Communication and Control, 4(3), 301–310. Porreca, A. E., Leporati, A., Mauri, G., & Zandron, C. (2011). P systems with elementary active membranes: Beyond NP and coNP. In M. Gheorghe, T. Hinze, Gh Păun, G. Rozenberg, & A. Salomaa (Eds.), 11th International Conference on Membrane Computing (pp. 338–347). CMC 2010, Springer, New York. Porreca, A. E., Leporati, A., Mauri, G., & Zandron, C. (2011). P systems with active membranes: Trading time for space. Natural Computing, 10(1), 167–182. Porreca, A. E., Leporati, A., Mauri, G., & Zandron, C. (2011). P systems with active membranes working in polynomial space. International Journal of Foundation of Computer Science, 22(1), 65–73. Porreca, A. E., Leporati, A., Mauri, G., & Zandron, C. (2012). P Systems Simulating Oracle Computations. In M. Gheorghe, G. Păun, A. Salomaa, G. Rozenberg, & S. Verlan (Eds.), 12th International Conference on Membrane Computing (pp. 346–358). CMC 2011, LNCS 7184, Springer, New York. Porreca, A. E., Leporati, A., Mauri, G., & Zandron, C. (2013). Sublinear Space P systems with Active Membranes. In E. Csuhaj-Varjú, M. Gheorghe, G. Rozenberg, A. Salomaa, & G. Vaszil (Eds.), 13th International Conference on Membrane Computing (pp. 342–357). CMC 2012, LNCS 7762, Springer, New York. Porreca, A. E., Mauri, G., & Zandron, C. (2006). Complexity classes for membrane systems. RAIRO-Theorerical Informatics and Applications, 40(2), 141–162. Porreca, A. E., Mauri, G., & Zandron, C. (2010). Non-confluence in divisionless P systems with active membranes. Theoretical Computer Science, 411, 878–887. Sosík, P. (2003). The computational power of cell division in P systems: Beating down parallel computers? Natural Computing, 2(3), 287–298. Sosík, P. (2019). P systems attacking hard problems beyond NP: A survey. Journal of Membrane Computing, 1(3), 198–208. https://doi.org/10.1007/s41965-019-00017-y. 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), 37–152. Sosík, P., Păun, A., Rodríguez-Patón, A., & Pérez, D. (2010). On the Power of Computing with Proteins on Membranes. In Gh Păun, M. J. Pérez-Jiménez, A. Riscos-Núñez, G. Rozenberg, & A. Salomaa (Eds.), 10th international Workshop on Membrane Computing (pp. 448–460). WMC 2009, LNCS 5957, Springer, New York. Valencia-Cabrera, L., Orellana-Martín, D., Martínez-del-Amor, M. A., Riscos-Núñez, A., & Pérez-Jiménez, M. J. (2017). Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation. Theoretical Computer Science, 701, 226–234. Valencia-Cabrera, L., Orellana-Martín, D., Martínez-del-Amor, M. A., Riscos-Núñez, A., & Pérez-Jiménez, M. J. (2017). Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes. Fundamenta Informaticae, 153(1–2), 147–172. Zandron, C., Ferretti, C., & Mauri, G. (2000). Solving NP-complete problems using P systems with active membranes. In I. Antoniou, C. S. Calude, & M. J. Dinneen (Eds.), Unconventional Models of Computation, UMC2K (pp. 289–301). Discrete Mathematics and Theoretical Computer Science: Springer, New York.