{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T00:28:34Z","timestamp":1791160114003,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540575290","type":"print"},{"value":"9783540482116","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57529-4_66","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:06:23Z","timestamp":1330261583000},"page":"326-337","source":"Crossref","is-referenced-by-count":30,"title":["Complexity results for 1-safe nets"],"prefix":"10.1007","author":[{"given":"Allan","family":"Cheng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javier","family":"Esparza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Luca Bernardinello and Fiorella De Cindio. A survey of basic net models and modular net classes. In Advances in Petri Nets 1992, pages 304\u2013351. Springer-Verlag (LNCS 609), 1992.","DOI":"10.1007\/3-540-55610-9_177"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Eike Best, Raymond Devillers, and Jon G. Hall. The Box calculus: a new causal algebra with multi-label communication. In Advances in Petri Nets 1992, pages 21\u201369. Springer-Verlag (LNCS 609), 1992.","DOI":"10.1007\/3-540-55610-9_167"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Eike Best and C\u00e9sar Fern\u00e1ndez. Nonsequential Processes \u2014 a Petri Net View. EATCS Monographs on Theoretical Computer Science Vol.13, 1988.","DOI":"10.1007\/978-3-642-73483-0_3"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Eike Best and P.S. Thiagarajan. Some classes of live and save Petri nets. In K. Voss, H.J. Genrich, and G. Rozenberg, editors, Advances in Petri Nets, pages 71\u201394. Springer-Verlag, 1987.","DOI":"10.1007\/978-3-642-72822-8_8"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Allan Cheng, Javier Esparza, and Jens Palsberg. Complexity results for 1-safe nets. Technical Report DAIMI PB-455, Computer Science Department, Aarhus University, September 1993.","DOI":"10.7146\/dpb.v22i455.6773"},{"key":"28_CR6","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/S0022-0000(71)80013-2","volume":"5","author":"F. Commoner","year":"1971","unstructured":"Fred Commoner, Anatole W. Holt, S. Even, and Amir Pnueli. Marked directed graphs. Journal of Computer and System Sciences, 5:511\u2013523, 1971.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02915446","volume":"26","author":"P. Degano","year":"1988","unstructured":"Pierpaolo Degano, Rocco De Nicola, and Ugo Montanari. A distributed operational semantics for CCS based on C\/E systems. Acta Informatica, 26:59\u201391, 1988.","journal-title":"Acta Informatica"},{"key":"28_CR8","unstructured":"J\u00f6rg Desel. A proof of the rank theorem. In Advances in Petri Nets 1992, pages 304\u2013351. Springer-Verlag (LNCS 609), 1992."},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"J\u00f6rg Desel and Javier Esparza. Shortest paths in reachability graphs. In Proc. Application and Theory of Petri Nets, pages 224\u2013241. Springer-Verlag (LNCS 691), 1993.","DOI":"10.1007\/3-540-56863-8_49"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Javier Esparza. Model checking using net unfoldings. In Proc. TAPSOFT'93, pages 613\u2013628. Springer-Verlag (LNCS 668), 1993.","DOI":"10.1007\/3-540-56610-4_93"},{"key":"28_CR11","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0304-3975(92)90299-U","volume":"102","author":"J. Esparza","year":"1992","unstructured":"Javier Esparza and Manuel Silva. A polynomial-time algorithm to decide liveness of bounded free choice nets. Theoretical Computer Science, 102:185\u2013205, 1992.","journal-title":"Theoretical Computer Science"},{"key":"28_CR12","unstructured":"Michael R. Garey and David S. Johnson. Computers and Intractability. Freeman, 1979."},{"key":"28_CR13","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF00264027","volume":"2","author":"H. J. Genrich","year":"1973","unstructured":"Hartmann J. Genrich and Kurt Lautenbach. Synchronisationsgraphen. Acta Informatica, 2:143\u2013161, 1973.","journal-title":"Acta Informatica"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Patrice Godefroid. Using partial orders to improve automatic verification methods. In Proc. CAV'90, 2nd Workshop on Computer-Aided Verification, pages 176\u2013185. Springer-Verlag (LNCS 531), 1990.","DOI":"10.1007\/BFb0023731"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Ursula Goltz. On representing CCS programs by finite Petri nets. In Proc. MFCS'88, Mathematical Foundations of Computer Science, pages 339\u2013350. Springer-Verlag (LNCS 324), 1988.","DOI":"10.1007\/BFb0017157"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Michel Hack. The recursive equivalence of the reachabilty problem and the liveness problem for Petri nets and vector addition systems. In Proc. 15th Annual Symposium on Switching and Automata Theory, pages 156\u2013164, 1974.","DOI":"10.1109\/SWAT.1974.28"},{"key":"28_CR17","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-3975(76)90008-6","volume":"2","author":"M. Hack","year":"1976","unstructured":"Michel Hack. The equality problem for vector addition systems is undecidable. Theoretical Computer Science, 2:77\u201395, 1976.","journal-title":"Theoretical Computer Science"},{"key":"28_CR18","unstructured":"John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, 1979."},{"key":"28_CR19","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/0022-0000(88)90013-X","volume":"37","author":"R. R. Howell","year":"1988","unstructured":"Rodney R. Howell and Louis E. Rosier. Completeness results for conflict-free vector replacement systems. Journal of Computer and System Sciences, 37:349\u2013366, 1988.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"28_CR20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(89)90053-4","volume":"64","author":"R. R. Howell","year":"1989","unstructured":"Rodney R. Howell and Louis E. Rosier. Problems concerning fairness and temporal logic for conflict-free Petri nets. Theoretical Computer Science, 64(3):305\u2013329, 1989.","journal-title":"Theoretical Computer Science"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Lalita Jategaonkar and Albert Meyer. Deciding true concurrency equivalences on finite safe nets. In Proc. ICALP'93, pages 519\u2013531, 1993.","DOI":"10.1007\/3-540-56939-1_99"},{"key":"28_CR22","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(77)90014-7","volume":"4","author":"N. D. Jones","year":"1977","unstructured":"Neil D. Jones, Lawrence H. Landweber, and Y. Edmund Lien. Complexity of some problems in Petri nets. Theoretical Computer Science, 4:277\u2013299, 1977.","journal-title":"Theoretical Computer Science"},{"key":"28_CR23","unstructured":"Richard J. Lipton. The reachability problem requires exponential space. Technical Report 62, Yale University, 1976."},{"key":"28_CR24","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"E. W. Mayr","year":"1984","unstructured":"Ernst W. Mayr. An algorithm for the general Petri net reachability problem. SIAM Journal on Computing, 13:441\u2013460, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"28_CR25","doi-asserted-by":"crossref","unstructured":"Kenneth L. McMillan. Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits. In Proc. CAV'92, Fourth Workshop on Computer-Aided Verification, pages 164\u2013174, 1992.","DOI":"10.1007\/3-540-56496-9_14"},{"key":"28_CR26","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0890-5401(90)90013-8","volume":"88","author":"J. Meseguer","year":"1990","unstructured":"Jos\u00e9 Meseguer and Ugo Montanari. Petri nets are monoids. Information and Computation, 88:105\u2013155, 1990.","journal-title":"Information and Computation"},{"issue":"4","key":"28_CR27","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1109\/5.24143","volume":"77","author":"T. Murata","year":"1989","unstructured":"Tadao Murata. Petri nets: Properties, analysis and applications. In Proc. of the IEEE, volume 77(4), pages 541\u2013580, 1989.","journal-title":"Proc. of the IEEE"},{"issue":"1","key":"28_CR28","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01783665","volume":"4","author":"M. Nielsen","year":"1990","unstructured":"Mogens Nielsen, Grzegorz Rozenberg, and P.S. Thiagarajan. Behavioural notions for elementary net systems. Distributed Computing, 4(1):45\u201357, 1990.","journal-title":"Distributed Computing"},{"key":"28_CR29","doi-asserted-by":"crossref","unstructured":"Ernst R. Olderog. Nets, Terms and Formulas. Cambridge University Press, 1991. Number 23 Tracts in Theoretical Computer Science.","DOI":"10.1017\/CBO9780511526589"},{"key":"28_CR30","doi-asserted-by":"crossref","unstructured":"Wolfgang Reisig. Petri Nets \u2014 An Introduction. EATCS Monographs in Computer Science Vol.4, 1985.","DOI":"10.1007\/978-3-642-69968-9"},{"key":"28_CR31","unstructured":"Iain A. Stewart. On the reachability problem for some classes of Petri nets. Research Report, University of Newcastle upon Tyne, 1992."},{"key":"28_CR32","doi-asserted-by":"crossref","unstructured":"P.S. Thiagarajan. Elementary net systems. In Advances in Petri Nets 1986, part I, pages 26\u201359. Springer-Verlag (LNCS 254), 1987.","DOI":"10.1007\/978-3-540-47919-2_3"},{"key":"28_CR33","doi-asserted-by":"crossref","unstructured":"Antti Valmari. Stubborn sets for reduced state space generation. In Grzegorz Rozenberg, editor, Advances in Petri Nets 1990, pages 491\u2013515. Springer-Verlag (LNCS 483), 1990.","DOI":"10.1007\/3-540-53863-1_36"},{"issue":"3","key":"28_CR34","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0890-5401(87)90032-0","volume":"72","author":"G. Winskel","year":"1987","unstructured":"Glynn Winskel. Petri nets, algebras, morphisms and compositionality. Information and Computation, 72(3):197\u2013238, 1987.","journal-title":"Information and Computation"},{"key":"28_CR35","doi-asserted-by":"crossref","unstructured":"Glynn Winskel and Mogens Nielsen. Models for concurrency. Technical Report DAIMI PB-429, Computer Science Department, Aarhus University, November 1992. To appear as a chapter in the Handbook of Logic and the Foundations of Computer Science, Oxford University Press.","DOI":"10.7146\/dpb.v21i429.6743"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57529-4_66.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:06:04Z","timestamp":1619571964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57529-4_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575290","9783540482116"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-57529-4_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}