{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:28Z","timestamp":1759637968431,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T00:00:00Z","timestamp":1575244800000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005881","name":"Emberi Eroforr\u00e1sok Miniszt\u00e9riuma","doi-asserted-by":"publisher","award":["TUDFO\/47138-1\/2019-ITM"],"award-info":[{"award-number":["TUDFO\/47138-1\/2019-ITM"]}],"id":[{"id":"10.13039\/501100005881","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["K 120558"],"award-info":[{"award-number":["K 120558"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Membr Comput"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>According to the P conjecture by Gh. P\u0103un, polarizationless P systems with active membranes cannot solve <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbf {NP}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>NP<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete problems in polynomial time. The conjecture is proved only in special cases yet. In this paper we consider the case where only elementary membrane division and dissolution rules are used and the initial membrane structure consists of one elementary membrane besides the skin membrane. We give a new approach based on the concept of object division polynomials introduced in this paper to simulate certain computations of these P systems. Moreover, we show how to compute efficiently the result of these computations using these polynomials.<\/jats:p>","DOI":"10.1007\/s41965-019-00024-z","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T11:54:00Z","timestamp":1575287640000},"page":"251-261","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A new method to simulate restricted variants of polarizationless P systems with active membranes"],"prefix":"10.1007","volume":"1","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":"G\u00e1bor","family":"Kolonits","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,2]]},"reference":[{"key":"24_CR1","first-page":"67","volume":"58","author":"A Alhazov","year":"2003","unstructured":"Alhazov, A., Mart\u00edn-Vide, C., & Pan, L. (2003). Solving a PSPACE-complete problem by P systems with restricted active membranes. Fundamenta Informaticae, 58, 67\u201377.","journal-title":"Fundamenta Informaticae"},{"issue":"2\u20133","key":"24_CR2","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, G. (2004). Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41(2\u20133), 111\u2013144.","journal-title":"Acta Informatica"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Alhazov, A., & P\u00e9rez-Jim\u00e9nez, M.J. (2007). Uniform solution of QSAT using polarizationless active membranes. In J. Durand-Lose, & M. Margenstern (Eds.), Machines, Computations, and Universality, MCU 2007, LNCS vol. 4664, pp. 122\u2013133.","DOI":"10.1007\/978-3-540-74593-8_11"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Cord\u00f3n-Franco, A., Guti\u00e9rrez-Naranjo, M.A., P\u00e9rez-Jim\u00e9nez, M.J., & Riscos-N\u00fa\u00f1ez, A. (2005). Exploring computation trees associated with P systems. In G. Mauri, G., Paun, M. J. P\u00e9rez-Jim\u00e9nez, G. Rozenberg, & Salomaa, (Eds.), Membrane Computing, 5th International Workshop, WMC 2004, LNCS vol. 3365, pp. 278\u2013286.","DOI":"10.1007\/978-3-540-31837-8_16"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Gazdag, Z. (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":"24_CR6","doi-asserted-by":"crossref","unstructured":"Gazdag, Z., & Guti\u00e9rrez-Naranjo, M.A. (2014). Solving the ST-connectivity problem with pure membrane computing techniques. In M. Gheorghe, G., Rozenberg, A., Salomaa, P., Sos\u00edk, & C., Zandron, (Eds.), Membrane Computing: 15th International Conference, LNCS vol. 8961, pp. 215\u2013228.","DOI":"10.1007\/978-3-319-14370-5_13"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Gazdag, Z., & 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":"24_CR8","doi-asserted-by":"crossref","unstructured":"Gazdag, Z., & 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"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Gazdag, Z., Kolonits, G., & Guti\u00e9rrez-Naranjo, M.A. (2014). Simulating Turing machines with polarizationless P systems with active membranes. In M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sos\u00edk, & C. Zandron, (Eds.), Membrane Computing: 15th International Conference, LNCS vol. 8961, pp. 229\u2013240.","DOI":"10.1007\/978-3-319-14370-5_14"},{"key":"24_CR10","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, G. P\u0103un, G. Rozenberg, & A. Salomaa (Eds.), Membrane Computing: 6th International Workshop, LNCS vol. 3850, pp. 224\u2013240.","DOI":"10.1007\/11603047_16"},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-319-28475-0_16","volume-title":"Membrane Computing","author":"G\u00e1bor Kolonits","year":"2015","unstructured":"Kolonits, G. (2015). A solution of horn-SAT with P systems using antimatter. In: Membrane Computing: 16th International Conference, LNCS vol. 9504, pp. 236\u2013250."},{"issue":"4","key":"24_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"},{"issue":"4","key":"24_CR13","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. (2009). Complexity aspects of polarizationless membrane systems. Natural Computing: An International Journal, 8(4), 703\u2013717.","journal-title":"Natural Computing: An International Journal"},{"key":"24_CR14","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, P. Sos\u00edk, & C. Zandron, (Eds.), Membrane Computing, 15th International Conference, LNCS vol. 8961, pp. 284\u2013299."},{"key":"24_CR15","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."},{"key":"24_CR16","unstructured":"Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2018). Solving QSAT in Sublinear Depth. In: Membrane Computing: 19th International Conference, LNCS vol. 11399, pp. 188\u2013201."},{"key":"24_CR17","unstructured":"Leporati, A., Zandron, C., Ferretti, C., & Mauri, G. (2009). Solving PSPACE-complete problems by polarizationless recognizer P systems with strong division and dissolution. Emerging Paradigms in Informatics, Systems and Communication, pp. 93\u201398."},{"key":"24_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, G. 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":"24_CR19","doi-asserted-by":"crossref","unstructured":"Murphy, N., & Woods, D. (2008). A Characterisation of NL using membrane systems without charges and dissolution. In C.S. Calude, J.F.G. da Costa, R. Freund, M. Oswald, & G. Rozenberg, (Eds.), Unconventional Computing: 7th International Conference, LNCS vol. 5204, pp. 164\u2013176.","DOI":"10.1007\/978-3-540-85194-3_14"},{"issue":"1","key":"24_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: An International Journal, 10(1), 613\u2013632.","journal-title":"Natural Computing: An International Journal"},{"issue":"2","key":"24_CR21","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":"24_CR22","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"},{"issue":"1","key":"24_CR23","first-page":"75","volume":"6","author":"G P\u0103un","year":"2001","unstructured":"P\u0103un, G. (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":"24_CR24","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."},{"key":"24_CR25","unstructured":"Porreca, A.E., Leporati, A., Mauri, G., & Zandron, C. (2012). Sublinear-space 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. 342\u2013357."},{"volume-title":"The Oxford Handbook of Membrane Computing","year":"2010","key":"24_CR26","unstructured":"P\u0103un, G., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford Handbook of Membrane Computing. Oxford, England: Oxford University Press."},{"key":"24_CR27","doi-asserted-by":"crossref","unstructured":"P\u00e9rez-Jim\u00e9nez, M.J., & Romero-Campero, F.J. (2005). Trading polarization for bi-stable catalysts in P systems with active membranes. In G. Mauri, G. P\u0103un, M.J. P\u00e9rez-Jim\u00e9nez, G. Rozenberg, & A. Salomaa, (eds.) Membrane Computing: 5th International Workshop, LNCS vol. 3365, pp. 373\u2013388.","DOI":"10.1007\/978-3-540-31837-8_24"},{"issue":"3","key":"24_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":"24_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"},{"issue":"3","key":"24_CR30","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"},{"issue":"1","key":"24_CR31","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":"24_CR32","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":"24_CR33","unstructured":"Zandron, C., Ferretti, C., & Mauri, G. (2001). Solving NP-complete problems using P systems with active membranes. Unconventional Models of Computation (pp. 289\u2013301), UMC\u20192K: Proceedings of the Second International Conference on Unconventional Models of Computation, London: Springer."}],"container-title":["Journal of Membrane Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41965-019-00024-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41965-019-00024-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41965-019-00024-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T20:15:22Z","timestamp":1606767322000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s41965-019-00024-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["24"],"URL":"https:\/\/doi.org\/10.1007\/s41965-019-00024-z","relation":{},"ISSN":["2523-8906","2523-8914"],"issn-type":[{"type":"print","value":"2523-8906"},{"type":"electronic","value":"2523-8914"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"25 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}