{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:07Z","timestamp":1725663247799},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_22","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:00:46Z","timestamp":1330203646000},"page":"234-243","source":"Crossref","is-referenced-by-count":6,"title":["Normal and sinkless Petri nets"],"prefix":"10.1007","author":[{"given":"Rodney R.","family":"Howell","sequence":"first","affiliation":[]},{"given":"Louis E.","family":"Rosier","sequence":"additional","affiliation":[]},{"given":"Hsu-Chun","family":"Yen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"22_CR1","unstructured":"H. Baker. Rabin's Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems. Memo 79, MIT Project MAC, Computer Structure Group, 1973."},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1090\/S0002-9939-1976-0396605-3","volume":"55","author":"I. Borosh","year":"1976","unstructured":"I. Borosh and L. Treybig. Bounds on positive integral solutions of linear Diophantine equations. Proc. AMS, 55:299\u2013304, March 1976.","journal-title":"Proc. AMS"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"E. Cardoza, R. Lipton, and A. Meyer. Exponential space complete problems for Petri nets and commutative semigroups. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing, pages 50\u201354, 1976.","DOI":"10.1145\/800113.803630"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/0020-0190(75)90020-4","volume":"3","author":"S. Crespi-Reghizzi","year":"1975","unstructured":"S. Crespi-Reghizzi and D. Mandrioli. A decidability theorem for a class of vector addition systems. Information Processing Letters, 3:78\u201380, 1975.","journal-title":"Information Processing Letters"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(80)90026-5","volume":"11","author":"J. Grabowski","year":"1980","unstructured":"J. Grabowski. The decidability of persistence for vector addition systems. Information Processing Letters, 11:20\u201323, 1980.","journal-title":"Information Processing Letters"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0022-0000(80)90009-4","volume":"20","author":"A. Ginzburg","year":"1980","unstructured":"A. Ginzburg and M. Yoeli. Vector addition systems and regular languages. J. of Computer and System Sciences, 20:277\u2013284, 1980.","journal-title":"J. of Computer and System Sciences"},{"key":"22_CR7","unstructured":"M. Hack. Petri Net Languages. Memo 124, MIT Project MAC, Computer Structure Group, 1975."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(76)90008-6","volume":"2","author":"M. Hack","year":"1976","unstructured":"M. Hack. The equality problem for vector addition systems is undecidable. Theoret. Comp. Sci., 2:77\u201395, 1976.","journal-title":"Theoret. Comp. Sci."},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0304-3975(79)90041-0","volume":"8","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoret. Comp. Sci., 8:135\u2013159, 1979.","journal-title":"Theoret. Comp. Sci."},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/0022-0000(88)90013-X","volume":"37","author":"R. Howell","year":"1988","unstructured":"R. Howell and L. Rosier. Completeness results for conflict-free vector replacement systems. J. of Computer and System Sciences, 37:349\u2013366, 1988.","journal-title":"J. of Computer and System Sciences"},{"key":"22_CR11","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-50580-6_30","volume-title":"Advances in Petri Nets 1988","author":"R. Howell","year":"1988","unstructured":"R. Howell and L. Rosier. On questions of fairness and temporal logic for conflict-free Petri nets. In G. Rozenberg, editor, Advances in Petri Nets 1988, pages 200\u2013226, Springer-Verlag, Berlin, 1988. LNCS 340."},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0304-3975(86)90026-5","volume":"46","author":"R. Howell","year":"1986","unstructured":"R. Howell, L. Rosier, D. Huynh, and H. Yen. Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states. Theoret. Comp. Sci., 46:107\u2013140, 1986.","journal-title":"Theoret. Comp. Sci."},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(87)90089-5","volume":"25","author":"R. Howell","year":"1987","unstructured":"R. Howell, L. Rosier, and H. Yen. An O(n1.5) algorithm to decide boundedness for conflict-free vector replacement systems. Information Processing Letters, 25:27\u201333, 1987.","journal-title":"Information Processing Letters"},{"key":"22_CR14","unstructured":"R. Howell, L. Rosier, and H. Yen. Normal and Sinkless Petri Nets. Technical Report TR-CS-88-14, Kansas State University, Manhattan, Kansas 66506, 1988."},{"key":"22_CR15","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979."},{"key":"22_CR16","first-page":"291","volume":"18","author":"D. Huynh","year":"1982","unstructured":"D. Huynh. The complexity of semilinear sets. Elektronische Informationsverarbeitung und Kybernetik, 18:291\u2013338, 1982.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"D. Huynh. The complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 405\u2013412, 1985.","DOI":"10.1145\/22145.22190"},{"key":"22_CR18","first-page":"147","volume":"22","author":"D. Huynh","year":"1986","unstructured":"D. Huynh. A simple proof for the \u03c3 2 P upper bound of the inequivalence problem for semilinear sets. Elektronische Informationsverarbeitung und Kybernetik, 22:147\u2013156, 1986.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(77)90014-7","volume":"4","author":"N. Jones","year":"1977","unstructured":"N. Jones, L. Landweber, and Y. Lien. Complexity of some problems in Petri nets. Theoret. Comp. Sci., 4:277\u2013299, 1977.","journal-title":"Theoret. Comp. Sci."},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"R. Kosaraju. Decidability of reachability in vector addition systems. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pages 267\u2013280, 1982.","DOI":"10.1145\/800070.802201"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"J. Lambert. Consequences of the decidability of the reachability problem for Petri nets. In Proceedings of the Eighth European Workshop on Application and Theory of Petri Nets, pages 451\u2013470, 1987. To appear in Theoret. Comp. Sci.","DOI":"10.1007\/3-540-50580-6_33"},{"key":"22_CR22","unstructured":"R. Lipton. The Reachability Problem Requires Exponential Space. Technical Report 62, Yale University, Dept. of CS., Jan. 1976."},{"key":"22_CR23","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1145\/322077.322079","volume":"25","author":"L. Landweber","year":"1978","unstructured":"L. Landweber and E. Robertson. Properties of conflict-free and persistent Petri nets. JACM, 25:352\u2013364, 1978.","journal-title":"JACM"},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF00289268","volume":"15","author":"E. Mayr","year":"1981","unstructured":"E. Mayr. Persistence of vector replacement systems is decidable. Acta Informatica, 15:309\u2013318, 1981.","journal-title":"Acta Informatica"},{"key":"22_CR25","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"E. Mayr","year":"1984","unstructured":"E. Mayr. An algorithm for the general Petri net reachability problem. SIAM J. Comput., 13:441\u2013460, 1984. A preliminary version of this paper was presented at the 13th Annual Symposium on Theory of Computing, 1981.","journal-title":"SIAM J. Comput."},{"key":"22_CR26","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1145\/322261.322271","volume":"28","author":"E. Mayr","year":"1981","unstructured":"E. Mayr and A. Meyer. The complexity of the finite containment problem for Petri nets. JACM, 28:561\u2013576, 1981.","journal-title":"JACM"},{"key":"22_CR27","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E. Mayr","year":"1982","unstructured":"E. Mayr and A. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46:305\u2013329, 1982.","journal-title":"Advances in Mathematics"},{"issue":"Suppl.","key":"22_CR28","first-page":"89","volume":"3","author":"H. M\u00fcller","year":"1981","unstructured":"H. M\u00fcller. On the reachability problem for persistent vector replacement systems. Computing, Suppl., 3:89\u2013104, 1981.","journal-title":"Computing"},{"key":"22_CR29","volume-title":"Petri Net Theory and the Modeling of Systems","author":"J. Peterson","year":"1981","unstructured":"J. Peterson. Petri Net Theory and the Modeling of Systems. Prentice Hall, Englewood Cliffs, NJ, 1981."},{"key":"22_CR30","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(78)90036-1","volume":"6","author":"C. Rackoff","year":"1978","unstructured":"C. Rackoff. The covering and boundedness problems for vector addition systems. Theoret. Comp. Sci., 6:223\u2013231, 1978.","journal-title":"Theoret. Comp. Sci."},{"key":"22_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69968-9","volume-title":"Petri Nets: An Introduction","author":"W. Reisig","year":"1985","unstructured":"W. Reisig. Petri Nets: An Introduction. Springer-Verlag, Heidelberg, 1985."},{"key":"22_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer. The polynomial-time hierarchy. Theoret. Comp. Sci., 3:1\u201322, 1977.","journal-title":"Theoret. Comp. Sci."},{"key":"22_CR33","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(81)90067-2","volume":"23","author":"R. Valk","year":"1981","unstructured":"R. Valk and G. Vidal-Naquet. Petri nets and regular languages. J. of Computer and System Sciences, 23:299\u2013325, 1981.","journal-title":"J. of Computer and System Sciences"},{"key":"22_CR34","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0304-3975(84)90038-0","volume":"31","author":"H. Yamasaki","year":"1984","unstructured":"H. Yamasaki. Normal Petri nets. Theoret. Comp. Sci., 31:307\u2013315, 1984.","journal-title":"Theoret. Comp. Sci."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T02:55:14Z","timestamp":1640919314000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}