{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T01:19:50Z","timestamp":1778548790741,"version":"3.51.4"},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,8]]},"abstract":" We consider the following definition (different from the standard definition in the literature) of \"maximal parallelism\" in the application of evolution rules in a P system G: Let R = {r1<\/jats:sub>, \u2026rk<\/jats:sub>} be the set of (distinct) rules in the system. G operates in maximally parallel mode if at each step of the computation, a maximal subset of R is applied, and at most one instance of any rule is used at every step (thus at most k rules are applicable at any step). We refer to this system as a maximally parallel system. We look at the computing power of P systems under three semantics of parallelism. For a positive integer n \u2264 k, define: <\/jats:p> n-Max-Parallel: At each step, nondeterministically select a maximal subset of at most n rules in R to apply (this implies that no larger subset is applicable). <\/jats:p> \u2264 n-Parallel: At each step, nondeterministically select any subset of at most n rules in R to apply. <\/jats:p> n-Parallel: At each step, nondeterministically select any subset of exactly n rules in R to apply. <\/jats:p> In all three cases, if any rule in the subset selected is not applicable, then the whole subset is not applicable. When n = 1, the three semantics reduce to the Sequential mode. <\/jats:p> We focus on two popular models of P systems: multi-membrane catalytic systems and communicating P systems. We show that for these systems, n-Max-Parallel mode is strictly more powerful than any of the following three modes: Sequential, \u2264 n-Parallel, or n-Parallel. For example, it follows from the result in [9] that a maximally parallel communicating P system is universal for n = 2. However, under the three limited modes of parallelism, the system is equivalent to a vector addition system, which is known to only define a recursive set. These generalize and refine the results for the case of 1-membrane systems recently reported in [3]. Some of the present results are rather surprising. For example, we show that a Sequential 1-membrane communicating P system can only generate a semilinear set, whereas with k membranes, it is equivalent to a vector addition system for any k \u2265 2 (thus the hierarchy collapses at 2 membranes - a rare collapsing result for nonuniversal P systems). We also give another proof (using vector addition systems) of the known result [8] that a 1-membrane catalytic system with only 3 catalysts and (non-prioritized) catalytic rules operating under 3-Max-Parallel mode can simulate any 2-counter machine M. Unlike in [8], our catalytic system needs only a fixed number of noncatalysts, independent of M. <\/jats:p> A simple cooperative system (SCO) is a P system where the only rules allowed are of the form a \u2192 v or of the form aa \u2192 v, where a is a symbol and v is a (possibly null) string of symbols not containing a. We show that a 9-Max-Parallel 1-membrane SCO is universal. <\/jats:p>","DOI":"10.1142\/s0129054105003236","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"683-705","source":"Crossref","is-referenced-by-count":10,"title":["ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS"],"prefix":"10.1142","volume":"16","author":[{"given":"OSCAR H.","family":"IBARRA","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}]},{"given":"HSU-CHUN","family":"YEN","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan 106, R.O.C."}]},{"given":"ZHE","family":"DANG","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"Grammar Systems: A Grammatical Approach to Distribution and Cooperation","author":"Csuhaj-Varju E.","year":"1994"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80003-7"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694011"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90041-0"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80022-9"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.10.028"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289268"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1693"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56196-2"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00136-6"},{"key":"rf18","volume-title":"Petri Net Theory and the Modeling of Systems","author":"Peterson J.","year":"1981"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:38:37Z","timestamp":1565138317000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":11,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1142\/S0129054105003236"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003236","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}