Characterizing PSPACE with shallow non-confluent P systems

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Simulating elementary active membranes, with an application to the P conjecture. In: Gheorghe M, Rozenberg G, Sosík P, Zandron C, editors. Membrane computing, 15th International conference, CMC 2014, lecture notes in computer science, vol. 8961. New York: Springer; 2014. p. 284–99.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Membrane division, oracles, and the counting hierarchy. Fund Inf. 2015;138(1–2):97–111.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Monodirectional P systems. Nat Comput. 2016;15(4):551–64.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. The counting power of P systems with antimatter. Theor Comput Sci. 2017;701:161–73.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Shallow non-confluent P systems. In: Leporati A, Rozenberg G, Salomaa A, Zandron C, editors. Membrane computing, 17th international conference, CMC 2016. Lecture notes in computer science, vol. 10105. New York: Springer; 2017. p. 307–16.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. A toolbox for simpler active membrane algorithms. Theor Comput Sci. 2017;673:42–57.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Solving QSAT in sublinear depth. In: Hinze T, Rozenberg G, Salomaa A, Zandron C editors. Membrane computing, CMC 2018. Lecture notes in computer science, vol 11399. Cham: Springer; 2019.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Subroutines in P systems and closure properties of their complexity classes. Theor Comput Sci. 2018.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. A survey on space complexity of P systems with active membranes. Int J Adv in Eng Sci Appl Math. 2018;10(3):221–9.

Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Characterising the complexity of tissue P systems with fission rules. J Comput Syst Sci. 2017;90:115–28.

Murphy N, Woods D. The computational power of membrane systems under tight uniformity conditions. Nat Comput. 2011;10(1):613–32.

Păun Gh, Rozenberg G, Salomaa A, editors. The Oxford handbook of membrane computing. Oxford: Oxford University Press; 2010.

Pérez-Jiménez MJ, Romero-Jiménez A, Sancho-Caparrini F. Complexity classes in models of cellular computing with membranes. Nat Comput. 2003;2(3):265–84.

Porreca AE, Leporati A, Mauri G, Zandron C. Recent complexity-theoretic results on P systems with active membranes. J Logic Comput. 2015;25(4):1047–71.

Porreca AE, Mauri G, Zandron C. Non-confluence in divisionless P systems with active membranes. Theor Comput Sci. 2010;411(6):878–87.

Sosík P. The computational power of cell division in P systems: Beating down parallel computers? Nat Comput. 2003;2(3):287–98.

Sosík P, Rodríguez-Patón A. Membrane computing and complexity theory: a characterization of PSPACE. J Comput Syst Sci. 2007;73(1):137–52.

Zandron C, Ferretti C, Mauri G. Solving NP-complete problems using P systems with active membranes. In: Antoniou I, Calude CS, Dinneen MJ, editors. Unconventional models of computation, UMC’2K, proceedings of the second international conference. New York: Springer; 2001. p. 289–301.