{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:07Z","timestamp":1725664027702},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540568636"},{"type":"electronic","value":"9783540477594"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56863-8_64","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T06:43:28Z","timestamp":1330238608000},"page":"513-531","source":"Crossref","is-referenced-by-count":1,"title":["A unified approach for reasoning about conflict-free Petri nets"],"prefix":"10.1007","author":[{"given":"Hsu-Chun","family":"Yen","sequence":"first","affiliation":[]},{"given":"Bow-Yaw","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Ming-Sheng","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"29_CR1","first-page":"1","volume":"583","author":"P. Alimonti","year":"1992","unstructured":"Alimonti, P., Feuerstain, E. and Nanni, U. Linear time algorithms for liveness and boundedness in conflict-free Petri nets. Proceedings of 1st Latin American Theoretical Informatics (LATIN'92), LNCS 583, pp. 1\u201314, 1992.","journal-title":"LNCS"},{"key":"29_CR2","unstructured":"Baker, H. 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."},{"issue":"3","key":"29_CR3","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0020-0190(75)90020-4","volume":"3","author":"S. Crespi-Reghizzi","year":"1975","unstructured":"Crespi-Reghizzi, S. and Mandrioli, D. A decidability theorem for a class of vector addition systems. Information Processing Letters, 3(3):78\u201380, 1975.","journal-title":"Information Processing Letters"},{"key":"29_CR4","first-page":"384","volume":"480","author":"J. Desel","year":"1991","unstructured":"Desel, J. and Esparza, J. Reachability in reversible free choice systems. Proceedings of the 8th Symposium on Theoretical Aspects of Computer Science (STACS'91), LNCS 480, pp. 384\u2013397, 1991.","journal-title":"LNCS"},{"issue":"6","key":"29_CR5","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0020-0190(92)90158-R","volume":"41","author":"J. Esparza","year":"1992","unstructured":"Esparza, J. A solution to the covering problem for 1-bounded conflict-free Petri nets. Information Processing Letters, 41(6):313\u2013319, 1992.","journal-title":"Information Processing Letters"},{"key":"29_CR6","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0304-3975(92)90299-U","volume":"102","author":"J. Esparza","year":"1992","unstructured":"Esparza, J. and Silva, M. A polynomial-time algorithm to decide liveness of bounded free choice nets. Theoret. Comp. Sci., 102:185\u2013205, 1992.","journal-title":"Theoret. Comp. Sci."},{"key":"29_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M. and Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Company Publishers, San Francisco, California, 1979."},{"issue":"1","key":"29_CR8","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(80)90026-5","volume":"11","author":"J. Grabowski","year":"1980","unstructured":"Grabowski, J. The decidability of persistence for vector addition systems. Information Processing Letters, 11(1):20\u201323, 1980.","journal-title":"Information Processing Letters"},{"key":"29_CR9","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-3975(76)90008-6","volume":"2","author":"M. Hack","year":"1976","unstructured":"Hack, M. The equality problem for vector addition systems is undecidable. Theoret. Comp. Sci., 2:77\u201395, 1976.","journal-title":"Theoret. Comp. Sci."},{"key":"29_CR10","volume-title":"TR-92-022","author":"M. Heiner","year":"1992","unstructured":"Heiner, M. Petri net based software validation prospects and limitations. International Computer Science Institute, Berkeley, California. TR-92-022, March, 1992."},{"key":"29_CR11","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(79)90041-0","volume":"8","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J. and Pansiot, J. On the reachability problem for 5-dimensional vector addition systems. Theoret. Comp. Sci., 8:135\u2013159, 1979.","journal-title":"Theoret. Comp. Sci."},{"key":"29_CR12","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/0022-0000(88)90013-X","volume":"37","author":"R. Howell","year":"1988","unstructured":"Howell, R. and Rosier, L. 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":"29_CR13","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":"Howell, R. and Rosier, L. On questions of fairness and temporal logic for conflictfree Petri nets. In G. Rozenberg, editor, Advances in Petri Nets 1988, pages 200\u2013226, Springer-Verlag, Berlin, 1988. LNCS 340."},{"key":"29_CR14","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-3975(86)90026-5","volume":"46","author":"R. Howell","year":"1986","unstructured":"Howell, R., Rosier, L., Huynh, D. and Yen, H. 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":"29_CR15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(87)90089-5","volume":"25","author":"R. Howell","year":"1987","unstructured":"Howell, R., Rosier, L. and Yen, H. 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":"29_CR16","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/0304-3975(91)90228-T","volume":"82","author":"R. Howell","year":"1991","unstructured":"Howell, R., Rosier, L. and Yen, H. A taxonomy of fairness and temporal logic problems for Petri nets. Theoret. Comp. Sci., 82:341\u2013372, 1991.","journal-title":"Theoret. Comp. Sci."},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Howell, R., Rosier, L. and Yen, H. Normal and sinkless Petri nets, in \u2018Proceedings of the 7th International Conference on the Fundamentals of Computation Theory,\u2019 pp. 234\u2013243, 1989. To appear in J. of Computer and System Sciences, 46, 1993.","DOI":"10.1007\/3-540-51498-8_22"},{"key":"29_CR18","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(77)90014-7","volume":"4","author":"N. Jones","year":"1977","unstructured":"Jones, N., Landweber, L. and Lien, Y. Complexity of some problems in Petri nets. Theoret. Comp. Sci., 4:277\u2013299, 1977.","journal-title":"Theoret. Comp. Sci."},{"issue":"no.5","key":"29_CR19","first-page":"1093","volume":"244","author":"L. Khachian","year":"1979","unstructured":"Khachian, L. A polynomial algorithm for linear programming. Doklady Akad. Nauk USSR, 244, no. 5(1979), 1093\u201396. Translated in Soviet Math. Doklady, 20, 191\u201394.","journal-title":"Doklady Akad. Nauk USSR"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Kosaraju, R. Decidability of reachability in vector addition systems. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp. 267\u2013280, 1982.","DOI":"10.1145\/800070.802201"},{"key":"29_CR21","unstructured":"Lipton, R. The reachability problem requires exponential space. Technical Report 62, Yale University, Dept. of CS., Jan. 1976."},{"issue":"3","key":"29_CR22","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1145\/322077.322079","volume":"25","author":"L. Landweber","year":"1978","unstructured":"Landweber, L. and Robertson, E. Properties of conflict-free and persistent Petri nets. JACM, 25(3):352\u2013364, 1978.","journal-title":"JACM"},{"issue":"3","key":"29_CR23","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"E. Mayr","year":"1984","unstructured":"Mayr, E. An algorithm for the general Petri net reachability problem. SIAM J. Comput., 13(3):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."},{"issue":"4","key":"29_CR24","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1109\/5.24143","volume":"77","author":"T. Murata","year":"1989","unstructured":"Murata, T. Petri nets: properties, analysis and applications. Proc. of the IEEE, 77(4): 541\u2013580, 1989.","journal-title":"Proc. of the IEEE"},{"key":"29_CR25","volume-title":"Petri Net Theory and the Modeling of Systems","author":"J. Peterson","year":"1981","unstructured":"Peterson, J. Petri Net Theory and the Modeling of Systems. Prentice Hall, Englewood Cliffs, NJ, 1981."},{"key":"29_CR26","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0304-3975(78)90036-1","volume":"6","author":"C. Rackoff","year":"1978","unstructured":"Rackoff, C. The covering and boundedness problems for vector addition systems. Theoret. Comp. Sci., 6:223\u2013231, 1978.","journal-title":"Theoret. Comp. Sci."},{"key":"29_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69968-9","volume-title":"Petri Nets: An Introduction","author":"W. Reisig","year":"1985","unstructured":"Reisig, W. Petri Nets: An Introduction. Springer-Verlag, Heidelberg, 1985."},{"key":"29_CR28","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00290730","volume":"19","author":"I. Suzuki","year":"1983","unstructured":"Suzuki, I. and Kasami, T. Three measures for synchronic dependence in Petri nets, Acta Informatica, 19:325\u2013338, 1983.","journal-title":"Acta Informatica"},{"key":"29_CR29","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/0022-0000(92)90013-9","volume":"44","author":"M. Silva","year":"1992","unstructured":"Silva, M. and Murata, T. B-Fairness and structural B-Fairness in Petri net models of concurrent systems J. of Computer and System Sciences, 44:447\u2013477, 1992.","journal-title":"J. of Computer and System Sciences"},{"key":"29_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L. The polynomial-time hierarchy. Theoret. Comp. Sci., 3:1\u201322, 1977.","journal-title":"Theoret. Comp. Sci."},{"key":"29_CR31","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1007\/BF00289715","volume":"21","author":"R. Valk","year":"1985","unstructured":"Valk, R. and Jantzen, M. The residue of vector sets with applications to decidability problems in Petri nets, Acta Informatica, 21:643\u2013674, 1985.","journal-title":"Acta Informatica"},{"key":"29_CR32","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0304-3975(84)90038-0","volume":"31","author":"H. Yamasaki","year":"1984","unstructured":"Yamasaki, H. Normal Petri nets. Theoret. Comp. Sci., 31:307\u2013315, 1984.","journal-title":"Theoret. Comp. Sci."},{"key":"29_CR33","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0020-0190(91)90225-7","volume":"38","author":"H. Yen","year":"1991","unstructured":"Yen, H. A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets. Information Processing Letters, 38:71\u201376, 1991.","journal-title":"Information Processing Letters"},{"issue":"1","key":"29_CR34","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0890-5401(92)90059-O","volume":"96","author":"H. Yen","year":"1992","unstructured":"Yen, H. A unified approach for deciding the existence of certain Petri net paths. Information and Computation, 96(1): 119\u2013137, 1992.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Application and Theory of Petri Nets 1993"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56863-8_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:06:23Z","timestamp":1605629183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56863-8_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540568636","9783540477594"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-56863-8_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}