{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T09:49:57Z","timestamp":1769852997003,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642114663","type":"print"},{"value":"9783642114670","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11467-0_10","type":"book-chapter","created":{"date-parts":[[2010,1,19]],"date-time":"2010-01-19T15:49:33Z","timestamp":1263916173000},"page":"125-148","source":"Crossref","is-referenced-by-count":19,"title":["A Computational Complexity Theory in Membrane Computing"],"prefix":"10.1007","author":[{"given":"Mario J.","family":"P\u00e9rez\u2013Jim\u00e9nez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-540-74593-8_11","volume-title":"Machines, Computations, and Universality","author":"A. Alhazov","year":"2007","unstructured":"Alhazov, A., P\u00e9rez\u2013Jim\u00e9nez, M.J.: Uniform solution of QSAT using polarizationless active membranes. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol.\u00a04664, pp. 122\u2013133. Springer, Heidelberg (2007)"},{"key":"10_CR2","unstructured":"Alhazov, A., Freund, R., P\u0103un, Gh.: P systems with active membranes and two polarizations. In: P\u0103un, Gh., et al. (eds.) Proc. Second Brainstorming Week on Membrane Computing, Report RGNC 01\/04, Sevilla, pp. 20\u201335 (2004)"},{"issue":"2-3","key":"10_CR3","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.: Trading polarizations for labels in P systems with active membranes. Acta Informaticae\u00a041(2-3), 111\u2013144 (2004)","journal-title":"Acta Informaticae"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Aspects of Molecular Computing","author":"A. Alhazov","year":"2003","unstructured":"Alhazov, A., Mart\u00edn\u2013Vide, C., Pan, L.: Solving graph problems by P systems with restricted elementary active membranes. In: Jonoska, N., P\u0103un, Gh., Rozenberg, G. (eds.) Aspects of Molecular Computing. LNCS, vol.\u00a02950, pp. 1\u201322. Springer, Heidelberg (2003)"},{"key":"10_CR5","first-page":"67","volume":"58","author":"A. Alhazov","year":"2003","unstructured":"Alhazov, A., Mart\u00edn\u2013Vide, C., Pan, L.: Solving a PSPACE\u2013complete problem by recognizing P systems with restricted active membranes. Fundamenta Informaticae\u00a058, 67\u201377 (2003)","journal-title":"Fundamenta Informaticae"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"D\u00edaz\u2013Pernil, D., Guti\u00e9rrez\u2013Naranjo, M.A., P\u00e9rez-Jim\u00e9nez, M.J., Romero\u2013Jim\u00e9nez, A.: Efficient simulation of tissue\u2013like P systems by transition cell\u2013like P systems. Natural Computing, \n                      http:\/\/dx.doi.org\/10.1007\/s11047-008-9102-z","DOI":"10.1007\/s11047-008-9102-z"},{"issue":"3","key":"10_CR7","first-page":"229","volume":"11","author":"D. D\u00edaz\u2013Pernil","year":"2008","unstructured":"D\u00edaz\u2013Pernil, D., P\u00e9rez\u2013Jim\u00e9nez, M.J., Riscos\u2013N\u00fa\u00f1ez, A., Romero\u2013Jim\u00e9nez, A.: Computational efficiency of cellular division in tissue-like membrane systems. Romanian Journal of Information Science and Technology\u00a011(3), 229\u2013241 (2008)","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"10_CR8","volume-title":"Computers and Intractability. A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. W.H. Freeman and Company, New York (1979)"},{"key":"10_CR9","unstructured":"Guti\u00e9rrez-Naranjo, R., P\u00e9rez-Jim\u00e9nez, M.J., Rius\u2013Font, M.: Characterizing tractability by tissue\u2013like P systems. In: Guti\u00e9rrez\u2013Escudero, R., et al. (eds.) Proc. Seventh Brainstorming Week on Membrane Computing, F\u00e9nix Editora, Seville, pp. 169\u2013180 (2009)"},{"issue":"9","key":"10_CR10","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00500-004-0397-0","volume":"9","author":"M.A. Guti\u00e9rrez-Naranjo","year":"2005","unstructured":"Guti\u00e9rrez-Naranjo, M.A., P\u00e9rez-Jim\u00e9nez, M.J., Riscos-N\u00fa\u00f1ez, A.: A fast P system for finding a balanced 2-partition. Soft Computing\u00a09(9), 673\u2013678 (2005)","journal-title":"Soft Computing"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/11603047_16","volume-title":"Membrane Computing","author":"M.A. Guti\u00e9rrez\u2013Naranjo","year":"2006","unstructured":"Guti\u00e9rrez\u2013Naranjo, M.A., P\u00e9rez\u2013Jim\u00e9nez, M.J., Riscos\u2013N\u00fa\u00f1ez, A., Romero\u2013Campero, F.J.: On the power of dissolution in P systems with active membranes. In: Freund, R., P\u0103un, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol.\u00a03850, pp. 224\u2013240. Springer, Heidelberg (2006)"},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1142\/9789812773036_0009","volume-title":"Formal Models, Languages and Applications","author":"M.A. Guti\u00e9rrez\u2013Naranjo","year":"2006","unstructured":"Guti\u00e9rrez\u2013Naranjo, M.A., P\u00e9rez\u2013Jim\u00e9nez, M.J., Riscos\u2013N\u00fa\u00f1ez, A., Romero\u2013Campero, F.J., Romero\u2013Jim\u00e9nez, A.: Characterizing tractability by cell\u2013like membrane systems. In: Subramanian, K.G., et al. (eds.) Formal Models, Languages and Applications, pp. 137\u2013154. World Scientific, Singapore (2006)"},{"issue":"4","key":"10_CR13","first-page":"357","volume":"2","author":"S.N. Krishna","year":"1999","unstructured":"Krishna, S.N., Rama, R.: A variant of P systems with active membranes: Solving NP\u2013complete problems. Romanian Journal of Information Science and Technology\u00a02(4), 357\u2013367 (1999)","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Leporati, A., Ferretti, C., Mauri, G., P\u00e9rez\u2013Jim\u00e9nez, M.J., Zandron, C.: Complexity aspects of polarizationless membrane systems. Natural Computing, \n                      http:\/\/dx.doi.org\/10.1007\/s11047-008-9100-1","DOI":"10.1007\/s11047-008-9100-1"},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/978-3-540-77312-2_23","volume-title":"Membrane Computing","author":"N. Murphy","year":"2007","unstructured":"Murphy, N., Woods, D.: Active membrane systems without charges and using only symetric elementary division characterise P. In: Eleftherakis, G., Kefalas, P., P\u0103un, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2007. LNCS, vol.\u00a04860, pp. 367\u2013384. Springer, Heidelberg (2007)"},{"issue":"1-2","key":"10_CR16","first-page":"551","volume":"4","author":"A. Obtulowicz","year":"2001","unstructured":"Obtulowicz, A.: Deterministic P systems for solving SAT problem. Romanian Journal of Information Science and Technology\u00a04(1-2), 551\u2013558 (2001)","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"10_CR17","unstructured":"Pan, L., Alhazov, A., Ishdorj, T.-O.: Further remarks on P systems with active membranes, separation, merging, and release rules. In: P\u0103un, Gh., et al. (eds.) Proc. Second Brainstorming Week on Membrane Computing, Report RGNC 01\/04, Sevilla, pp. 316\u2013324 (2004)"},{"issue":"5","key":"10_CR18","first-page":"630","volume":"10","author":"L. Pan","year":"2004","unstructured":"Pan, L., Ishdorj, T.-O.: P systems with active membranes and separation rules. Journal of Universal Computer Science\u00a010(5), 630\u2013649 (2004)","journal-title":"Journal of Universal Computer Science"},{"key":"10_CR19","unstructured":"Pan, L., P\u00e9rez-Jim\u00e9nez, M.J.: Computational complexity of tissue\u2013like P systems with cell separation (submitted, 2009)"},{"key":"10_CR20","first-page":"187","volume-title":"Unconventional Models of Computation","author":"A. P\u0103un","year":"2000","unstructured":"P\u0103un, A.: On P systems with membrane division. In: Antoniou, I., et al. (eds.) Unconventional Models of Computation, pp. 187\u2013201. Springer, London (2000)"},{"issue":"1","key":"10_CR21","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jcss.1999.1693","volume":"61","author":"G.. P\u0103un","year":"2000","unstructured":"P\u0103un, Gh.: Computing with membranes. Journal of Computer and System Sciences\u00a061(1), 108\u2013143 (2000); Turku Center for CS-TUCS Report No. 208 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56196-2","volume-title":"Membrane Computing. An Introduction","author":"G.. P\u0103un","year":"2002","unstructured":"P\u0103un, Gh.: Membrane Computing. An Introduction. Springer, Berlin (2002)"},{"issue":"1","key":"10_CR23","first-page":"75","volume":"6","author":"G.. P\u0103un","year":"2001","unstructured":"P\u0103un, Gh.: P systems with active membranes: Attacking NP\u2013complete problems. Journal of Automata, Languages and Combinatorics\u00a06(1), 75\u201390 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"10_CR24","first-page":"94","volume-title":"Unconventional Models of Computation","author":"G.. P\u0103un","year":"2000","unstructured":"P\u0103un, Gh.: Computing with membranes. Attacking NP\u2013complete problems. In: Antoniou, I., et al. (eds.) Unconventional Models of Computation, pp. 94\u2013115. Springer, London (2000)"},{"key":"10_CR25","unstructured":"P\u0103un, Gh.: Further twenty six open problems in membrane computing. In: Guti\u00e9rrez-Naranjo, M.A., et al. (eds.) Proc. Third Brainstorming Week on Membrane Computing, Report RGNC 01\/04, F\u00e9nix Editora, Sevilla, pp. 249\u2013262 (2005)"},{"key":"10_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-540-31837-8_5","volume-title":"Membrane Computing","author":"M.J. P\u00e9rez\u2013Jim\u00e9nez","year":"2005","unstructured":"P\u00e9rez\u2013Jim\u00e9nez, M.J.: An approach to computational complexity in membrane computing. In: Mauri, G., P\u0103un, G., Jes\u00fas P\u00e9rez-J\u00edmenez, M., Rozenberg, G., Salomaa, A. (eds.) WMC 2004. LNCS, vol.\u00a03365, pp. 85\u2013109. Springer, Heidelberg (2005)"},{"issue":"4","key":"10_CR27","first-page":"367","volume":"23","author":"M.J. P\u00e9rez-Jim\u00e9nez","year":"2005","unstructured":"P\u00e9rez-Jim\u00e9nez, M.J., Riscos-N\u00fa\u00f1ez, A.: Solving the Subset-Sum problem by active membranes. New Generation Computing\u00a023(4), 367\u2013384 (2005)","journal-title":"New Generation Computing"},{"key":"10_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/978-3-540-24619-0_19","volume-title":"Membrane Computing","author":"M.J. P\u00e9rez-Jim\u00e9nez","year":"2004","unstructured":"P\u00e9rez-Jim\u00e9nez, M.J., Riscos-N\u00fa\u00f1ez, A.: A linear\u2013time solution to the Knapsack problem using P systems with active membranes. In: Mart\u00edn-Vide, C., Mauri, G., P\u0103un, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2003. LNCS, vol.\u00a02933, pp. 250\u2013268. Springer, Heidelberg (2004)"},{"issue":"4","key":"10_CR29","first-page":"423","volume":"11","author":"M.J. P\u00e9rez-Jim\u00e9nez","year":"2006","unstructured":"P\u00e9rez-Jim\u00e9nez, M.J., Romero-Jim\u00e9nez, A., Sancho-Caparrini, F.: A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics\u00a011(4), 423\u2013434 (2006); A preliminary version in Csuhaj-Varj\u00fa, E., et al. (eds.) Proc. Fifth International Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, Budapest, Hungary, July 12-14, pp. 284\u2013294 (2003)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"10_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/978-3-540-31834-7_25","volume-title":"Machines, Computations, and Universality","author":"M.J. P\u00e9rez-Jim\u00e9nez","year":"2005","unstructured":"P\u00e9rez-Jim\u00e9nez, M.J., Romero\u2013Campero, F.J.: Attacking the common algorithmic problem by recognizer P systems. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol.\u00a03354, pp. 304\u2013315. Springer, Heidelberg (2005)"},{"issue":"5","key":"10_CR31","first-page":"650","volume":"10","author":"M.J. P\u00e9rez\u2013Jim\u00e9nez","year":"2004","unstructured":"P\u00e9rez\u2013Jim\u00e9nez, M.J., Romero\u2013Campero, F.J.: An efficient family of P systems for packing items into bins. Journal of Universal Computer Science\u00a010(5), 650\u2013670 (2004)","journal-title":"Journal of Universal Computer Science"},{"key":"10_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/978-3-540-31837-8_24","volume-title":"Membrane Computing","author":"M.J. P\u00e9rez\u2013Jim\u00e9nez","year":"2005","unstructured":"P\u00e9rez\u2013Jim\u00e9nez, M.J., Romero-Campero, F.J.: Trading polarizations for bi-stable catalysts in P systems with active membranes. In: Mauri, G., P\u0103un, G., Jes\u00fas P\u00e9rez-J\u00edmenez, M., Rozenberg, G., Salomaa, A. (eds.) WMC 2004. LNCS, vol.\u00a03365, pp. 373\u2013388. Springer, Heidelberg (2005)"},{"issue":"3","key":"10_CR33","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1025449224520","volume":"2","author":"M.J. P\u00e9rez\u2013Jim\u00e9nez","year":"2003","unstructured":"P\u00e9rez\u2013Jim\u00e9nez, M.J., Romero\u2013Jim\u00e9nez, A., Sancho\u2013Caparrini, F.: Complexity classes in cellular computing with membranes. Natural Computing\u00a02(3), 265\u2013285 (2003)","journal-title":"Natural Computing"},{"key":"10_CR34","unstructured":"Porreca, A.E.: Computational Complexity Classes for Membrane Systems, Master Degree Thesis, Universita\u2019 di Milano-Bicocca, Italy (2008)"},{"issue":"2","key":"10_CR35","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1051\/ita:2006001","volume":"40","author":"A.E. Porreca","year":"2006","unstructured":"Porreca, A.E., Mauri, G., Zandron, C.: Complexity classes for membrane systems. Informatique th\u00e9orique et applications\u00a040(2), 141\u2013162 (2006)","journal-title":"Informatique th\u00e9orique et applications"},{"key":"10_CR36","unstructured":"Riscos\u2013N\u00fa\u00f1ez, A.: Cellular Programming: efficient resolution of NP\u2013complete numerical problems. PhD. Thesis, University of Sevilla, Spain (2004)"},{"key":"10_CR37","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\u2013Pat\u00f3n, A.: Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences\u00a073, 137\u2013152 (2007)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"10_CR38","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1023\/A:1025401325428","volume":"2","author":"P. Sos\u00edk","year":"2003","unstructured":"Sos\u00edk, P.: The computational power of cell division. Natural Computing\u00a02(3), 287\u2013298 (2003)","journal-title":"Natural Computing"},{"key":"10_CR39","series-title":"Lecture Notes in Computer Science","first-page":"263","volume-title":"Membrane dissolution and division in P","author":"D. Woods","year":"2009","unstructured":"Woods, D., Murphy, N., P\u00e9rez-Jim\u00e9nez, M.J., Riscos-N\u00fa\u00f1ez, A.: Membrane dissolution and division in P. LNCS, vol.\u00a05715, pp. 263\u2013277. Springer, Heidelberg (2009)"},{"key":"10_CR40","first-page":"289","volume-title":"Unconventional Models of Computation","author":"C. Zandron","year":"2000","unstructured":"Zandron, C., Ferretti, C., Mauri, G.: Solving NP\u2013complete problems using P systems with active membranes. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, pp. 289\u2013301. Springer, Heidelberg (2000)"},{"issue":"1","key":"10_CR41","first-page":"79","volume":"87","author":"C. Zandron","year":"2008","unstructured":"Zandron, C., Leporati, A., Ferretti, C., Mauri, G., P\u00e9rez\u2013Jim\u00e9nez, M.J.: On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. Fundamenta Informaticae\u00a087(1), 79\u201391 (2008)","journal-title":"Fundamenta Informaticae"}],"container-title":["Lecture Notes in Computer Science","Membrane Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11467-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,18]],"date-time":"2023-02-18T03:14:26Z","timestamp":1676690066000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11467-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114663","9783642114670"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11467-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}