{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T00:04:06Z","timestamp":1774915446530,"version":"3.50.1"},"reference-count":16,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,29]],"date-time":"2013-07-29T00:00:00Z","timestamp":1375056000000},"content-version":"vor","delay-in-days":6053,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Electronic Notes in Theoretical Computer Science"],"published-print":{"date-parts":[[1997]]},"DOI":"10.1016\/s1571-0661(05)80423-2","type":"journal-article","created":{"date-parts":[[2005,5,19]],"date-time":"2005-05-19T09:46:30Z","timestamp":1116495990000},"page":"15-24","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":9,"special_numbering":"C","title":["Cyclic Petri Net Reachability Sets are Semi-linear Effectively Constructible"],"prefix":"10.1016","volume":"9","author":[{"given":"Zakaria","family":"Bouziane","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Finkel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0661(05)80423-2_BIB1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0304-3975(77)90059-7","article-title":"\u201cDecidability problems on the strong connectivity of Petri net reachability sets\u201d","volume":"4","author":"Araki","year":"1977","journal-title":"TCS"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB2","unstructured":"Bouziane Z. \u201cAlgorithmes primitifs r\u00e9cursifs et probl\u00e8mes EXPSPACE-complets dans les r\u00e9seaux de Petri cycliques\u201d, Th\u00e8se de Doctorat de 1'ENS de Cachan, November 1996."},{"key":"10.1016\/S1571-0661(05)80423-2_BIB3","unstructured":"Bouziane Z., Finkel F. \u201cThe equivalence problem for commutative semigroups and reversible Petri nets is complete in exponential space under log-lin reducibility\u201c, Presented at the International Conference in Semigroups and Related Topics at Kunming, China, August 1995 (Springer Verlag Proceeding 1997)."},{"key":"10.1016\/S1571-0661(05)80423-2_BIB4","doi-asserted-by":"crossref","unstructured":"Cardoza E. Lipton R. Meyer A.\u201dExponential space complete problems for Petri nets and commutative semigroups\u201c, Proc. of the 8th annual ACM Symposium on Theory of Computing, pp. 50-54, 1976.","DOI":"10.1145\/800113.803630"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB5","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/S0022-0000(71)80013-2","article-title":"\u201cMarked directed graphs\u201d","volume":"5","author":"Commoner","year":"1971","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB6","series-title":"\u201cFree choice Petri nets\u201d","author":"Desel","year":"1995"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB7","article-title":"\u201cDecidability issues for Petri nets\u201d","volume":"52","author":"Esparza","year":"1994","journal-title":"Bulletin EATCS"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB8","doi-asserted-by":"crossref","unstructured":"Hack M. \u201cThe equality problem for vector addition systems is undecidable\u201d, Computation structures Group Memo 121, Project MAC, M.I.T. April 1975. Also TCS 2 1976 (77-95).","DOI":"10.1016\/0304-3975(76)90008-6"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB9","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/0022-0000(88)90013-X","article-title":"\u201cCompleteness results for conflict-free vector replacement systems\u201d","volume":"37","author":"Howell","year":"1988","journal-title":"Journal of Computer and System Sciences"},{"issue":"No.4","key":"10.1016\/S1571-0661(05)80423-2_BIB10","article-title":"\u201cParallel program schemata\u201d","volume":"Vol. 3","author":"Karp","year":"1969","journal-title":"J. of Computer and System Science"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB11","unstructured":"Koppenhagen E., Mayr E. \u201cThe complexity of the equivalence problem for commutative semigroups\u201d, Technical Report TUM-I9603, 1996."},{"key":"10.1016\/S1571-0661(05)80423-2_BIB12","doi-asserted-by":"crossref","unstructured":"Kosaraju R. \u201cDecidability of reachability in Vector Addition Systems\u201d, Proc. of the 14th Annual ACM Symposium on Theory of Computing pp. 267-280, 1982.","DOI":"10.1145\/800070.802201"},{"issue":"3","key":"10.1016\/S1571-0661(05)80423-2_BIB13","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1137\/0213029","article-title":"\u201cAn algorithm for the general Petri net reachability problem\u201d","volume":"13","author":"Mayr","year":"1984","journal-title":"SIAM J. Compu."},{"key":"10.1016\/S1571-0661(05)80423-2_BIB14","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","article-title":"\u201cThe complexity of the word problems for commutative semigroups and polynomial ideals\u201d","volume":"46","author":"Mayr","year":"1982","journal-title":"Advances in Mathematics"},{"key":"10.1016\/S1571-0661(05)80423-2_BIB15","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0304-3975(78)90036-1","article-title":"\u201cThe covering and boundedness problems for vector addition systems\u201d","volume":"6","author":"Rackoff","year":"1978","journal-title":"in Theoretical Computer Science"},{"issue":"No. 3","key":"10.1016\/S1571-0661(05)80423-2_BIB16","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(81)90067-2","article-title":"\u201cPetri nets and regular languages\u201d","volume":"Vol. 23","author":"Valk","year":"1981","journal-title":"J. of Computer and System Sciences"}],"container-title":["Electronic Notes in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066105804232?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066105804232?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:07:05Z","timestamp":1761610025000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571066105804232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"references-count":16,"alternative-id":["S1571066105804232"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0661(05)80423-2","relation":{},"ISSN":["1571-0661"],"issn-type":[{"value":"1571-0661","type":"print"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Cyclic Petri Net Reachability Sets are Semi-linear Effectively Constructible","name":"articletitle","label":"Article Title"},{"value":"Electronic Notes in Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S1571-0661(05)80423-2","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1997 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}