{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:20:37Z","timestamp":1777645237431,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"1-2","license":[{"start":{"date-parts":[[2015,6,1]],"date-time":"2015-06-01T00:00:00Z","timestamp":1433116800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p>\n                    Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to P\n                    <jats:sup>PP<\/jats:sup>\n                    = P\n                    <jats:sup>#P<\/jats:sup>\n                    , the class of problems solvable in polynomial time by deterministic Turing machines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between P\n                    <jats:sup>PP<\/jats:sup>\n                    and PSPACE. In particular, for each integer k \u2265 0 we provide a lower bound to the computing power of P systems of depth k.\n                  <\/jats:p>","DOI":"10.3233\/fi-2015-1201","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T01:35:54Z","timestamp":1575336954000},"page":"97-111","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":18,"title":["Membrane Division, Oracles, and the Counting Hierarchy"],"prefix":"10.1177","volume":"138","author":[{"given":"Alberto","family":"Leporati","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 degli Studi di Milano-Bicocca, Viale Sarca 336\/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Manzoni","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 degli Studi di Milano-Bicocca, Viale Sarca 336\/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giancarlo","family":"Mauri","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 degli Studi di Milano-Bicocca, Viale Sarca 336\/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio E.","family":"Porreca","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 degli Studi di Milano-Bicocca, Viale Sarca 336\/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claudio","family":"Zandron","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u00e0 degli Studi di Milano-Bicocca, Viale Sarca 336\/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2015,6]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2015-1201","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2015-1201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:31:44Z","timestamp":1777444304000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2015-1201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":0,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.3233\/FI-2015-1201"],"URL":"https:\/\/doi.org\/10.3233\/fi-2015-1201","relation":{"is-cited-by":[{"id-type":"doi","id":"10.1007\/s11047-016-9565-2","asserted-by":"object"}]},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}