{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,11]],"date-time":"2024-05-11T05:10:10Z","timestamp":1715404210728},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p>In the standard definition of a P system, a computation step consists of a parallel application of a \"maximal\" set of nondeterministically chosen rules. Referring to this system as a parallel P system, we consider in this paper a sequential P system, in which each step consists of an application of a single nondeterministically chosen rule. We show the following:<\/jats:p><jats:p>1. For 1-membrane purely catalytic systems (pure CS's), the sequential version is strictly weaker than the parallel version in that the former defines (i.e., generates) exactly the semilinear sets, whereas the latter is known to define nonrecursive sets.<\/jats:p><jats:p>2. For 1-membrane communicating P systems (CPS's), the sequential version can only define a proper subclass of the semilinear sets, whereas the parallel version is known to define nonrecursive sets.<\/jats:p><jats:p>3. Adding a new type of rule of the form: ab \u2192 a<jats:sub>x<\/jats:sub>b<jats:sub>y<\/jats:sub>c<jats:sub>come<\/jats:sub>d<jats:sub>come<\/jats:sub>to the CPS (a natural generalization of the rule ab \u2192 a<jats:sub>x<\/jats:sub>b<jats:sub>y<\/jats:sub>c<jats:sub>come<\/jats:sub>in the original model), where x, y \u2208 {here, out}, to the sequential 1-membrane CPS makes it equivalent to a vector addition system.<\/jats:p><jats:p>4. Sequential 1-membrane symport\/antiport systems (SA's) are equivalent to vector addition systems, contrasting the known result that the parallel versions can define nonrecursive sets.<\/jats:p><jats:p>5. Sequential 1-membrane SA's whose rules have radius 1, (1,1), (1,2) (i.e., of the form (a, out), (a, in), (a, out; b, in), (a, out; bc, in)) generate exactly the semilinear sets. However, if the rules have radius 1, (1,1), (2,1) (i.e., of the form (ab, out; c, in)), the SA's can only generate a proper subclass of the semilinear sets.<\/jats:p>","DOI":"10.1142\/s0129054105003340","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T11:41:41Z","timestamp":1129203701000},"page":"867-881","source":"Crossref","is-referenced-by-count":8,"title":["ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE"],"prefix":"10.1142","volume":"16","author":[{"given":"ZHE","family":"DANG","sequence":"first","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA"}]},{"given":"OSCAR H.","family":"IBARRA","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"crossref","first-page":"13","DOI":"10.3233\/FI-1997-3112","volume":"31","author":"Esparza J.","journal-title":"Fundamenta Informatica"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.029"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90041-0"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80022-9"},{"key":"rf11","first-page":"167","volume":"11","author":"Ibarra O.","journal-title":"Theoretical Computer Science"},{"key":"rf12","first-page":"317","volume":"8","author":"Martin-Vide C.","journal-title":"Journal of Universal Computer Science"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289268"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037362"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1693"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56196-2"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00136-6"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T08:14:26Z","timestamp":1586506466000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":12,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S0129054105003340"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003340","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}