{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T18:08:20Z","timestamp":1765994900716,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T00:00:00Z","timestamp":1633392000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T00:00:00Z","timestamp":1633392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["NKFIH-1279-2\/2020"],"award-info":[{"award-number":["NKFIH-1279-2\/2020"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100015763","name":"University of Szeged","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100015763","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Membr Comput"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It is known that polarizationless P systems with active membranes can solve <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {PSPACE}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>PSPACE<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete problems in polynomial time without using in-communication rules but using the classical (also called strong) non-elementary membrane division rules. In this paper, we show that this holds also when in-communication rules are allowed but strong non-elementary division rules are replaced with weak non-elementary division rules, a type of rule which is an extension of elementary membrane divisions to non-elementary membranes. Since it is known that without in-communication rules, these P systems can solve\u00a0in polynomial time\u00a0only problems in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {P}^{\\text {NP}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>P<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mtext>NP<\/mml:mtext>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, our result proves that these rules serve as a borderline between <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {P}^{\\text {NP}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>P<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mtext>NP<\/mml:mtext>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {PSPACE}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>PSPACE<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> concerning the computational power of these P systems.<\/jats:p>","DOI":"10.1007\/s41965-021-00082-2","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T21:45:01Z","timestamp":1633470301000},"page":"258-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On the power of P systems with active membranes using weak non-elementary membrane division"],"prefix":"10.1007","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5617-8743","authenticated-orcid":false,"given":"Zsolt","family":"Gazdag","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K\u00e1roly","family":"Hajagos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Szabolcs","family":"Iv\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,5]]},"reference":[{"key":"82_CR1","doi-asserted-by":"crossref","unstructured":"Alhazov, A., P\u00e9rez-Jim\u00e9nez, M.J. (2007). Uniform solution of QSAT using polarizationless active membranes. International Conference on Machines, Computations and Universality, 122\u2013133.","DOI":"10.1007\/978-3-540-74593-8_11"},{"key":"82_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s41965-021-00074-2","volume":"3","author":"A Alhazov","year":"2021","unstructured":"Alhazov, A., Leporati, A., Manzoni, L., Mauri, G., & Zandron, C. (2021). Alternative space definitions for P systems with active membranes. Journal of Membrane Computing, 3, 87\u201396.","journal-title":"Journal of Membrane Computing"},{"key":"82_CR3","first-page":"67","volume":"58","author":"A Alhazov","year":"2003","unstructured":"Alhazov, A., Mart\u00edn-Vide, C., & Pan, L. (2003). Solving a $$\\rm PSPACE$$-complete problem by P systems with restricted active membranes. Fundamenta Informaticae, 58, 67\u201377.","journal-title":"Fundamenta Informaticae"},{"issue":"2\u20133","key":"82_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00236-004-0153-z","volume":"41","author":"A Alhazov","year":"2004","unstructured":"Alhazov, A., Pan, L., & P\u0103un, Gh. (2004). Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41(2\u20133), 111\u2013144.","journal-title":"Acta Informatica"},{"issue":"2","key":"82_CR5","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/s41965-020-00040-4","volume":"2","author":"K Bu\u00f1o","year":"2020","unstructured":"Bu\u00f1o, K., & Adorna, H. (2020). Distributed computation of a kP system with active membranes for SAT using clause completion. Journal of Membrane Computing, 2(2), 108\u2013120.","journal-title":"Journal of Membrane Computing"},{"key":"82_CR6","doi-asserted-by":"crossref","unstructured":"Gazdag, Zs. (2014). Solving SAT by P systems with active membranes in linear time in the number of variables. In: A. Alhazov, S. Cojocaru, M. Gheorghe, Y. Rogozhin, G. Rozenberg, A. Salomaa (Eds.), Membrane Computing: 14th International Conference, LNCS (vol. 8340, pp. 189\u2013205)","DOI":"10.1007\/978-3-642-54239-8_14"},{"key":"82_CR7","doi-asserted-by":"crossref","unstructured":"Gazdag, Zs., Kolonits, G. (2013). A new approach for solving SAT by P systems with active membranes. In: E. Csuhaj-Varj\u00fa, M. Gheorghe, G. Rozenberg, A. Salomaa, G. Vaszil (Eds.), Membrane Computing: 13th International Conference, LNCS (vol. 7762, pp. 195\u2013207)","DOI":"10.1007\/978-3-642-36751-9_14"},{"key":"82_CR8","doi-asserted-by":"crossref","unstructured":"Gazdag, Zs., Kolonits, G. (2017). Remarks on the computational power of some restricted variants of P systems with active membranes. In: A. Leporati, G. Rozenberg, A. Salomaa, C. Zandron (Eds.), Membrane Computing, 17th International Conference, LNCS (vol. 10105, pp. 209\u2013232)","DOI":"10.1007\/978-3-319-54072-6_14"},{"issue":"4","key":"82_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s41965-019-00024-z","volume":"1","author":"ZS Gazdag","year":"2019","unstructured":"Gazdag, Zs., & Kolonits, G. (2019). A new method to simulate restricted variants of polarizationless P systems with active membranes. Journal of Membrane Computing, 1(4), 251\u2013261.","journal-title":"Journal of Membrane Computing"},{"key":"82_CR10","doi-asserted-by":"publisher","DOI":"10.4324\/9780203204887","volume-title":"Introduction to logic","author":"HJ Gensler","year":"2002","unstructured":"Gensler, H. J. (2002). Introduction to logic. Routledge."},{"key":"82_CR11","doi-asserted-by":"crossref","unstructured":"Gutierrez-Naranjo, M.A., Perez-Jimenez, M.J., Riscos-N\u00fa\u00f1ez, A., Romero-Campero, F.J. (2006). On the power of dissolution in P systems with active membranes. In: R. Freund, Gh. P\u0103un, G. Rozenberg, A. Salomaa (eds.), Membrane computing: 6th international workshop, LNCS (vol. 3850, pp. 224\u2013240)","DOI":"10.1007\/11603047_16"},{"issue":"4","key":"82_CR12","first-page":"357","volume":"2","author":"SN Krishna","year":"1999","unstructured":"Krishna, S. N., & Rama, R. (1999). A variant of P systems with active membranes: Solving NP-complete problems. Romanian Journal of Information Science and Technology, 2(4), 357\u2013367.","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"82_CR13","doi-asserted-by":"crossref","unstructured":"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\u00edk, C. Zandron (Eds.), Membrane computing \u2013 15th international conference, CMC15, LNCS (vol. 8961, pp. 284\u2013299)","DOI":"10.1007\/978-3-319-14370-5_18"},{"key":"82_CR14","doi-asserted-by":"crossref","unstructured":"Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C. (2016). Monodirectional P systems. Natural Computing, 15, 551\u2013564","DOI":"10.1007\/s11047-016-9565-2"},{"key":"82_CR15","doi-asserted-by":"crossref","unstructured":"Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C. (2017). Solving a special case of the P conjecture using dependency graphs with dissolution. In: M. Gheorghe, G. Rozenberg, A. Salomaa, C. Zandron (eds.), Membrane computing: 18th international conference, LNCS (vol. 10725, pp. 196\u2013213)","DOI":"10.1007\/978-3-319-73359-3_13"},{"issue":"4","key":"82_CR16","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/s11047-008-9100-1","volume":"8","author":"A Leporati","year":"2009","unstructured":"Leporati, A., Ferretti, C., Mauri, G., P\u00e9rez-Jim\u00e9nez, M. J., & Zandron, C. (2009). Complexity aspects of polarizationless membrane systems. Natural Computing, 8(4), 703\u2013717.","journal-title":"Natural Computing"},{"key":"82_CR17","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s41965-019-00011-4","volume":"1","author":"A Leporati","year":"2019","unstructured":"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, 75\u201384.","journal-title":"Journal of Membrane Computing"},{"key":"82_CR18","doi-asserted-by":"crossref","unstructured":"Murphy, N., Woods, D. (2007). Active membrane systems without charges and using only symmetric elementary division characterise P. In: G. Eleftherakis, P. Kefalas, Gh. P\u0103un, G. Rozenberg, A. Salomaa (eds.), Membrane computing: 8th international workshop, LNCS (vol. 4860, pp. 367\u2013384)","DOI":"10.1007\/978-3-540-77312-2_23"},{"key":"82_CR19","doi-asserted-by":"crossref","unstructured":"Murphy, N., Woods, D. (2009). On acceptance conditions for membrane systems: Characterisations of $$\\mathbf{L}$$ and $$\\mathbf{NL}$$. In T. Neary, D. Woods, T. Seda, N. Murphy (eds.), Proceedings international workshop on the complexity of simple programs, Cork, Ireland, Volume 1 of Electronic Proceedings in Theoretical Computer Science., Open Publishing Association (pp. 172\u2013184)","DOI":"10.4204\/EPTCS.1.17"},{"issue":"1","key":"82_CR20","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s11047-010-9244-7","volume":"10","author":"N Murphy","year":"2011","unstructured":"Murphy, N., & Woods, D. (2011). The computational power of membrane systems under tight uniformity conditions. Natural Computing, 10(1), 613\u2013632.","journal-title":"Natural Computing"},{"issue":"1\u20132","key":"82_CR21","doi-asserted-by":"publisher","first-page":"129","DOI":"10.3233\/FI-2014-1095","volume":"134","author":"N Murphy","year":"2014","unstructured":"Murphy, N., & Woods, D. (2014). Uniformity is weaker than semi-uniformity for some membrane systems. Fundamental Information, 134(1\u20132), 129\u2013152.","journal-title":"Fundamental Information"},{"key":"82_CR22","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s41965-020-00058-8","volume":"2","author":"D Orellana-Mart\u00edn","year":"2020","unstructured":"Orellana-Mart\u00edn, D., & Riscos-N\u00fanez, A. (2020). Seeking computational efficiency boundaries: The P\u0103un\u2019s conjecture. Journal of Membrane Computing, 2, 323\u2013331.","journal-title":"Journal of Membrane Computing"},{"issue":"2","key":"82_CR23","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00236-006-0018-8","volume":"43","author":"L Pan","year":"2006","unstructured":"Pan, L., & Alhazov, A. (2006). Solving HPP and SAT by P systems with active membranes and separation rules. Acta Informatica, 43(2), 131\u2013145.","journal-title":"Acta Informatica"},{"issue":"9","key":"82_CR24","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1007\/s00500-004-0399-y","volume":"9","author":"L Pan","year":"2004","unstructured":"Pan, L., Alhazov, A., & Ishdorj, T.-O. (2004). Further remarks on P systems with active membranes, separation, merging, and release rules. Soft Computing, 9(9), 686\u2013690.","journal-title":"Soft Computing"},{"key":"82_CR25","unstructured":"P\u0103un, Gh. (2005). Further twenty six open problems in membrane computing. In: Third Brainstorming Week on Membrane Computing, (pp. 249\u2013262). F\u00e9nix Editora, Sevilla"},{"issue":"1","key":"82_CR26","first-page":"75","volume":"6","author":"Gh P\u0103un","year":"2001","unstructured":"P\u0103un, Gh. (2001). P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics, 6(1), 75\u201390.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"82_CR27","doi-asserted-by":"crossref","unstructured":"P\u0103un, Gh., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford Handbook of Membrane Computing. Oxford University Press.","DOI":"10.1007\/978-3-642-11467-0"},{"issue":"3","key":"82_CR28","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1025449224520","volume":"2","author":"MJ P\u00e9rez-Jim\u00e9nez","year":"2003","unstructured":"P\u00e9rez-Jim\u00e9nez, M. J., Romero-Jim\u00e9nez, \u00c1., & Sancho-Caparrini, F. (2003). Complexity classes in models of cellular computing with membranes. Natural Computing, 2(3), 265\u2013285.","journal-title":"Natural Computing"},{"issue":"4","key":"82_CR29","first-page":"423","volume":"11","author":"MJ P\u00e9rez-Jim\u00e9nez","year":"2006","unstructured":"P\u00e9rez-Jim\u00e9nez, M. J., Romero-Jim\u00e9nez, \u00c1., & Sancho-Caparrini, F. (2006). A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics, 11(4), 423\u2013434.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"82_CR30","volume-title":"Formal languages","author":"A Salomaa","year":"1973","unstructured":"Salomaa, A. (1973). Formal languages. Academic Press."},{"issue":"3","key":"82_CR31","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1023\/A:1025401325428","volume":"2","author":"P Sos\u00edk","year":"2003","unstructured":"Sos\u00edk, P. (2003). The computational power of cell division in P systems. Natural Computing, 2(3), 287\u2013298.","journal-title":"Natural Computing"},{"key":"82_CR32","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/s41965-019-00017-y","volume":"1","author":"P Sos\u00edk","year":"2019","unstructured":"Sos\u00edk, P. (2019). P systems attacking hard problems beyond NP: A survey. Journal of Membrane Computing, 1, 198\u2013208.","journal-title":"Journal of Membrane Computing"},{"issue":"1","key":"82_CR33","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.jcss.2006.10.001","volume":"73","author":"P Sos\u00edk","year":"2007","unstructured":"Sos\u00edk, P., & Rodr\u00edguez-Pat\u00f3n, A. (2007). Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences, 73(1), 137\u2013152.","journal-title":"Journal of Computer and System Sciences"},{"key":"82_CR34","doi-asserted-by":"crossref","unstructured":"Woods, D., Murphy, N., P\u00e9rez-Jim\u00e9nez, M.J., Riscos-N\u00fa\u00f1ez, A. (2009). Membrane dissolution and division in P. In: C.S. Calude, J.F.G. da Costa, N. Dershowitz, E. Freire, G. Rozenberg (Eds.), Unconventional computation: 8th international conference, LNCS (vol. 5715, pp. 262\u2013276)","DOI":"10.1007\/978-3-642-03745-0_28"},{"key":"82_CR35","doi-asserted-by":"crossref","unstructured":"Zandron, C., Ferretti, C., Mauri, G. (2001). Solving NP-complete problems using P systems with active membranes. In: Unconventional models of computation, UMC\u20192K: Proceedings of the second international conference on unconventional models of computation (pp. 289\u2013301). Springer London, London","DOI":"10.1007\/978-1-4471-0313-4_21"},{"key":"82_CR36","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s41965-020-00039-x","volume":"2","author":"C Zandron","year":"2020","unstructured":"Zandron, C. (2020). Bounding the space in P systems with active membranes. Journal of Membrane Computing, 2, 137\u2013145.","journal-title":"Journal of Membrane Computing"}],"container-title":["Journal of Membrane Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41965-021-00082-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41965-021-00082-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41965-021-00082-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,9]],"date-time":"2021-12-09T09:22:29Z","timestamp":1639041749000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41965-021-00082-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,5]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["82"],"URL":"https:\/\/doi.org\/10.1007\/s41965-021-00082-2","relation":{},"ISSN":["2523-8906","2523-8914"],"issn-type":[{"type":"print","value":"2523-8906"},{"type":"electronic","value":"2523-8914"}],"subject":[],"published":{"date-parts":[[2021,10,5]]},"assertion":[{"value":"5 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}