{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T15:31:56Z","timestamp":1781105516654,"version":"3.54.1"},"reference-count":13,"publisher":"IGI Global Scientific Publishing","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,7,1]]},"abstract":"<p>P systems with active membranes have the ability of solving computationally hard problems. In this paper, the authors prove that uniform families of P systems with active membranes operating in polynomial time can solve the whole class of PP decision problems, without using nonelementary membrane division or dissolution rules. This result also holds for families having a stricter uniformity condition than the usual one.<\/p>","DOI":"10.4018\/jncr.2011070104","type":"journal-article","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T12:42:31Z","timestamp":1319028151000},"page":"35-48","source":"Crossref","is-referenced-by-count":14,"title":["Elementary Active Membranes Have the Power of Counting"],"prefix":"10.4018","volume":"2","author":[{"given":"Antonio E.","family":"Porreca","sequence":"first","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano\u2013Bicocca, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto","family":"Leporati","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano\u2013Bicocca, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giancarlo","family":"Mauri","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano\u2013Bicocca, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claudio","family":"Zandron","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano\u2013Bicocca, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"jncr.2011070104-0","doi-asserted-by":"crossref","unstructured":"Alhazov, A., Burtseva, L., Cojocaru, S., & Rogozhin, Y. (2009). Solving PP-complete and #P-complete problems by P systems with active membranes. In D. Corne, P. Frisco, G. P\u0103un, G. Rozenberg, & A. Salomaa (Eds.), Proceedings of the International Conference on Membrane Computing (LNCS 5391, pp. 108-117).","DOI":"10.1007\/978-3-540-95885-7_8"},{"key":"jncr.2011070104-1","first-page":"67","article-title":"Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes.","volume":"58","author":"A.Alhazov","year":"2003","journal-title":"Fundamenta Informaticae"},{"key":"jncr.2011070104-2","author":"M. R.Garey","year":"1979","journal-title":"Computers and intractability: A guide to the theory of NP-completeness"},{"key":"jncr.2011070104-3","unstructured":"Murphy, N., & Porreca, A. E. (2010). First steps towards linking membrane depth and the polynomial hierarchy. In Proceedings of the Eighth Brainstorming Week on Membrane Computing (pp. 255-266)."},{"key":"jncr.2011070104-4","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-010-9244-7"},{"key":"jncr.2011070104-5","author":"C. M.Papadimitriou","year":"1994","journal-title":"Computational complexity"},{"key":"jncr.2011070104-6","first-page":"75","article-title":"P systems with active membranes: Attacking NP-complete problems. Journal of Automata","volume":"6","author":"G.P\u0103un","year":"2001","journal-title":"Languages and Combinatorics"},{"key":"jncr.2011070104-7","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025449224520"},{"key":"jncr.2011070104-8","doi-asserted-by":"crossref","unstructured":"Porreca, A. E., Leporati, A., Mauri, G., & Zandron, C. (2010). P systems with elementary active membranes: Beyond NP and coNP. In M. Gheorghe, T. Hinze, G. Paun, G. Rozenberg, & A. Salomaa (Eds.), Proceedings of the 11th International Conference on Membrane Computing (LNCS 6501, pp. 338-347).","DOI":"10.1007\/978-3-642-18123-8_26"},{"key":"jncr.2011070104-9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025401325428"},{"key":"jncr.2011070104-10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.001"},{"key":"jncr.2011070104-11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","author":"H.Vollmer","year":"1999","journal-title":"Introduction to circuit complexity: A uniform approach"},{"key":"jncr.2011070104-12","doi-asserted-by":"crossref","unstructured":"Zandron, C., Ferretti, C., & Mauri, G. (2001). Solving NP-complete problems using P systems with active membranes. In Proceedings of the Second International Conference on Unconventional Models of Computation (pp. 289-301).","DOI":"10.1007\/978-1-4471-0313-4_21"}],"container-title":["International Journal of Natural Computing Research"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=58065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T16:30:12Z","timestamp":1654101012000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jncr.2011070104"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2011,7,1]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"URL":"https:\/\/doi.org\/10.4018\/jncr.2011070104","relation":{},"ISSN":["1947-928X","1947-9298"],"issn-type":[{"value":"1947-928X","type":"print"},{"value":"1947-9298","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,1]]}}}