{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:16:32Z","timestamp":1726409792167},"publisher-location":"Berlin, Heidelberg","reference-count":64,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540334606"},{"type":"electronic","value":"9783540334613"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/978-3-540-33461-3_14","type":"book-chapter","created":{"date-parts":[[2006,10,19]],"date-time":"2006-10-19T13:37:55Z","timestamp":1161265075000},"page":"343-373","source":"Crossref","is-referenced-by-count":0,"title":["Hsu-Chun Yen"],"prefix":"10.1007","member":"297","reference":[{"key":"14_CR1_14","doi-asserted-by":"crossref","unstructured":"T. Agerwala and M. Flynn. Comments on capabilities, limitations and \u2018correctness\u2019 of Petri nets, Proc. of 1st Annual Symposium on Computer Architecture, 1973,81-86.","DOI":"10.1145\/800123.803973"},{"key":"14_CR2_14","unstructured":"H. Baker. Rabin\u2019s proof of the undecidability of the reachability set inclusion problem of vector addition systems, Computation Structures Group Memo 79, Project MAC, MIT, July 1973."},{"key":"14_CR3_14","doi-asserted-by":"publisher","first-page":"299","DOI":"10.2307\/2041711","volume":"55","author":"I. Borosh","year":"1976","unstructured":"I. Borosh, and L. Treybig. Bounds on positive integral solutions of linear Diophantine equations, Proc. Amer. Math. Soc. 55 (1976), 299-304.","journal-title":"Proc. Amer. Math. Soc."},{"key":"14_CR4_14","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF01178259","volume":"32","author":"L. Cherkasova","year":"1995","unstructured":"L. Cherkasova, R. Howell and L. Rosier. Bounded self-stabilizing Petri nets, Acta Informatica, 32 (1995), 189-207.","journal-title":"Acta Informatica"},{"key":"14_CR5_14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(86)90169-6","volume":"43","author":"P. Clote","year":"1986","unstructured":"P. Clote. On the finite containment problem for Petri nets, Theoretical Computer Science, 43 (1986), 99-105.","journal-title":"Theoretical Computer Science"},{"key":"14_CR6_14","doi-asserted-by":"publisher","first-page":"233","DOI":"10.2307\/2318447","volume":"80","author":"M. Davis","year":"1973","unstructured":"M. Davis. Hilbert\u2019s tenth problem is unsolvable, American Mathematical Monthly, 80 (1973), 233-269.","journal-title":"American Mathematical Monthly"},{"key":"14_CR7_14","doi-asserted-by":"crossref","unstructured":"J. Desel and J. Esparza. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511526558"},{"key":"14_CR8_14","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E. Dijkstra","year":"1974","unstructured":"E. Dijkstra. Self-stabilizing systems in spite of distributed control, C. ACM, 17 (1974),643-644.","journal-title":"C. ACM"},{"key":"14_CR9_14","first-page":"301","volume-title":"Languages and Programming, LNCS 1644","author":"C. Dufourd","year":"1999","unstructured":"C. Dufourd, P. Jancar and P. Schnoebelen. Boundedness of reset P\/T nets, Int\u2019l Colloquium on Automata, Languages and Programming, LNCS 1644, SpringerVerlag, Berlin, 1999, 301-310."},{"key":"14_CR10_14","first-page":"24","volume":"30","author":"J. Esparza","year":"1997","unstructured":"J. Esparza. Petri nets, commutative context-free grammars and basic parallel processes, Fundamenta Informaticae, 30 (1997), 24-41.","journal-title":"Fundamenta Informaticae"},{"key":"14_CR11_14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s002360050074","volume":"34","author":"J. Esparza","year":"1997","unstructured":"J. Esparza. Decidability of model checking for infinite-state concurrent systems, Acta Informatica, 34 (1997), 85-107.","journal-title":"Acta Informatica"},{"key":"14_CR12_14","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/3-540-65306-6_20","volume-title":"Lectures on Petri Nets I: Basic Models. Advances in Petri Nets","author":"J. Esparza","year":"1998","unstructured":"J. Esparza. Decidability and complexity of Petri net problems : an introduction, Lectures on Petri Nets I: Basic Models. Advances in Petri Nets (G. Rozenberg, W. Reisig, eds.), LNCS 1491, Springer-Verlag, Berlin, 1998, 374-V428."},{"key":"14_CR13_14","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/BFb0054314","volume-title":"Proc. of Latin American Theoretical INformatics (LATIN), LNCS 1380","author":"A. Finkel","year":"1998","unstructured":"A. Finkel and P. Schnoebelen. Fundamental structures in well-structured infinite transition systems, Proc. of Latin American Theoretical INformatics (LATIN), LNCS 1380, Springer-Verlag, Berlin, 1998, 102-118."},{"issue":"3","key":"14_CR14_14","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1145\/146637.146681","volume":"39","author":"S. German","year":"1992","unstructured":"S. German and A. Sistla. Reasoning about systems with many processes, J. ACM 39, 3 (1992), 675-735.","journal-title":"J. ACM"},{"key":"14_CR15_14","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg. The Mathematical Theory of Context-Free Languages, New York: McGraw-Hill, 1966."},{"issue":"1","key":"14_CR16_14","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, Inf. Process. Lett. 11, 1 (1980), 20-23.","journal-title":"Inf. Process. Lett."},{"key":"14_CR17_14","first-page":"102","volume-title":"On the complexity of the linear time mu-calculus for Petri nets, 18th International Conference on Application and Theory of Petri Nets, LNCS 1248","author":"P. Habermehl","year":"1997","unstructured":"P. Habermehl. On the complexity of the linear time mu-calculus for Petri nets, 18th International Conference on Application and Theory of Petri Nets, LNCS 1248, Springer-Verlag, Berlin, 1997, 102-116."},{"key":"14_CR18_14","doi-asserted-by":"crossref","unstructured":"M. Hack. The recursive equivalence of the reachability problem and the liveness problem for Petri nets and vector addition systems, FOCS, 1974, 156-164.","DOI":"10.1109\/SWAT.1974.28"},{"key":"14_CR19_14","unstructured":"M. Hack. The equality problem for vector addition systems is undecidable, C.S.C. Memo 121, Project MAC, MIT, 1975."},{"key":"14_CR20_14","unstructured":"M. Hack. Decidability questions for Petri nets, PhD dissertation, Dept. of Elec- trical Engineering, MIT, 1975."},{"issue":"2","key":"14_CR21_14","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, Theoretical Computer Science, 8, 2 (1979), 135-159.","journal-title":"Theoretical Computer Science"},{"issue":"2-3","key":"14_CR22_14","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, D. Huynh, L. Rosier and H. Yen. Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, Theoretical Computer Science, 46, 2-3 (1986), 107-140.","journal-title":"Theoretical Computer Science"},{"key":"14_CR23_14","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1006\/inco.1993.1055","volume":"106","author":"R. Howell","year":"1993","unstructured":"R. Howell, P. Jancar and L. Rosier. Completeness results for single path Petri nets, Information and Computation 106 (1993), 253-265.","journal-title":"Information and Computation"},{"issue":"3","key":"14_CR24_14","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(89)90053-4","volume":"64","author":"R. Howell","year":"1989","unstructured":"R. Howell and L. Rosier. Problems concerning fairness and temporal logic for conflict-free Petri nets, Theoretical Computer Science 64, 3 (1989), 305-329.","journal-title":"Theoretical Computer Science"},{"key":"14_CR25_14","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/0304-3975(91)90228-T","volume":"82","author":"R. Howell","year":"1991","unstructured":"R. Howell, L. Rosier and H. Yen. A taxonomy of fairness and temporal logic problems for Petri nets, Theoretical Computer Science, 82 (1991), 341-372.","journal-title":"Theoretical Computer Science"},{"key":"14_CR26_14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-0000(93)90046-Y","volume":"46","author":"L. RHowell","year":"1993","unstructured":"RHowell, L. Rosier and H. Yen. Normal and sinkless Petri nets, Journal of Computer and System Sciences 46 (1993), 1-26.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR27_14","first-page":"454","volume-title":"Undecidable equivalences for basic parallel processes, TACS 94, LNCS 789","author":"H. Huttel","year":"1994","unstructured":"H. Huttel. Undecidable equivalences for basic parallel processes, TACS 94, LNCS 789, Springer-Verlag, Berlin, 1994, 454-464."},{"key":"14_CR28_14","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0019-9958(83)80022-9","volume":"57","author":"D. Huynh","year":"1983","unstructured":"D. Huynh. Commutative grammars: the complexity of uniform word problems, Information and Control 57 (1983), 21-39.","journal-title":"Information and Control"},{"issue":"1","key":"14_CR29_14","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"O. Ibarra","year":"1978","unstructured":"O. Ibarra. Reversal-bounded multicounter machines and their decision problems, JACM 25, 1 (1978), 116-133.","journal-title":"JACM"},{"key":"14_CR30_14","doi-asserted-by":"crossref","unstructured":"A. Ichikawa and K. Hiraishi. Analysis and control of discrete event systems represented by Petri nets, LNCS 103, Springer-Verlag, 1987, 115-134.","DOI":"10.1007\/BFb0042308"},{"key":"14_CR31_14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(90)90006-4","volume":"74","author":"P. Jancar","year":"1990","unstructured":"P. Jancar. Decidability of a temporal logic problem for Petri nets, Theoretical Computer Science 74 (1990), 71-93.","journal-title":"Theoretical Computer Science"},{"key":"14_CR32_14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0304-3975(00)00100-6","volume":"256","author":"P. Jancar","year":"2001","unstructured":"P. Jancar. Non-primitive recursive complexity and undecidability for Petri net equivalences, Theoretical Computer Science 256 (2001), 23-30.","journal-title":"Theoretical Computer Science"},{"key":"14_CR33_14","first-page":"413","volume-title":"Complexity of place\/transition nets, Advances in Petri nets 86, LNCS 254","author":"M. Jantzen","year":"1986","unstructured":"M. Jantzen. Complexity of place\/transition nets, Advances in Petri nets 86, LNCS 254, Springer-Verlag, Berlin, 1986, 413-435."},{"key":"14_CR34_14","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(81)90049-9","volume":"14","author":"K. Jensen","year":"1981","unstructured":"K. Jensen. Coloured Petri Nets and the Invariant-Method, Theor. Comp. Science 14 (1981),317-336.","journal-title":"Theor. Comp. Science"},{"key":"14_CR35_14","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, Theoretical Computer Science 4:277-299, 1977.","journal-title":"Theoretical Computer Science"},{"key":"14_CR36_14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0022-0000(69)80011-5","volume":"3","author":"R. Karp","year":"1969","unstructured":"R. Karp and R. Miller. Parallel program schemata, Journal of Computer and System Sciences 3 (1969), 167-195.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR37_14","unstructured":"R. Keller. Vector replacement systems: a formalism for modelling asynchronous systems, Tech. Rept. 117, Computer Science Lab., Princeton Univ. 1972."},{"key":"14_CR38_14","doi-asserted-by":"crossref","unstructured":"R. Kosaraju. Decidability of reachability in vector addition systems, Proc. the 14th Annual ACM Symposium on Theory of Computing, 1982, 267-280.","DOI":"10.1145\/800070.802201"},{"issue":"3","key":"14_CR39_14","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, 3 (1978), 352-364.","journal-title":"JACM"},{"key":"14_CR40_14","unstructured":"R. Lipton. The reachability problem requires exponential space, Technical Re- port 62, Yale University, Dept. of CS., Jan. 1976."},{"key":"14_CR41_14","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 Infor- mattica 15 (1981), 309-318.","journal-title":"Acta Infor- mattica"},{"key":"14_CR42_14","doi-asserted-by":"crossref","unstructured":"E. Mayr. An algorithm for the general Petri net reachability problem, STOC, 1981,238-246.","DOI":"10.1145\/800076.802477"},{"key":"14_CR43_14","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 (1984), 441-460.","journal-title":"SIAM J. Comput."},{"key":"14_CR44_14","volume-title":"Decidability and complexity of model checking problems for infinite- state systems, PhD thesis","author":"R. Mayr","year":"1998","unstructured":"R. Mayr. Decidability and complexity of model checking problems for infinite- state systems, PhD thesis, Computer Science Dept., TU-Munich, Germany, April 1998."},{"issue":"3","key":"14_CR45_14","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, J. ACM, 28, 3 (1981), 561-576.","journal-title":"J. ACM"},{"key":"14_CR46_14","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0304-3975(84)90029-X","volume":"32","author":"K. McAloon","year":"1984","unstructured":"K. McAloon. Petri nets and large finite sets, Theoretical Computer Science 32 (1984),173-183.","journal-title":"Theoretical Computer Science"},{"key":"14_CR47_14","unstructured":"P. Merlin. A study of the recoverability of computing systems, PhD thesis, Dept. of Information and COmputer Science, Univ. of California at Irvine, 1974."},{"key":"14_CR48_14","first-page":"426","volume-title":"Decidability of reachability in persistent vector replacement systems, 9th Symp. on Math. Found. of Computer Science, LNCS 88","author":"H. Muller","year":"1980","unstructured":"H. Muller. Decidability of reachability in persistent vector replacement systems, 9th Symp. on Math. Found. of Computer Science, LNCS 88, Springer-Verlag, Berlin, 1980, 426-438."},{"key":"14_CR49_14","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1109\/5.24143","volume":"4","author":"T. Murata","year":"1989","unstructured":"T. Murata. Petri nets: properties, analysis and applications, Proc. of the IEEE, 77,4 (1989),541-580.","journal-title":"Proc. of the IEEE, 77"},{"key":"14_CR50_14","unstructured":"H. Ols\u00e9n. Automatic verification of Petri nets in a CLP framework, Ph.D. Thesis, Dept. of Computer and Information Science, IDA, Link\u00f6ping Univ., 1997."},{"key":"14_CR51_14","volume-title":"Coordination of asynchronous events, PhD thesis","author":"S. Patil","year":"1970","unstructured":"S. Patil. Coordination of asynchronous events, PhD thesis, Dept. of Elec. Eng., MIT, Cambridge, Mass., May. 1970."},{"issue":"1","key":"14_CR52_14","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jcss.1999.1693","volume":"61","author":"Gh. Paun","year":"2000","unstructured":"Gh. Paun. Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108-143.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR53_14","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":"14_CR54_14","volume-title":"Kommunikation mit Automaten, Dissertation, Rheinisch-Westfalisches Institut fur","author":"C. Petri","year":"1962","unstructured":"C. Petri. Kommunikation mit Automaten, Dissertation, Rheinisch-Westfalisches Institut fur. Intrumentelle Mathematik an der Universitat Bonn, Bonn. 1962."},{"key":"14_CR55_14","first-page":"92","volume-title":"welchem die Addition als einzige Operation hervortritt","author":"M. Presburger","year":"1929","unstructured":"M. Presburger. Uber die Vollstandigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Comptes Rendus du I congres de Mathematiciens des Pays Slaves, Warszawa, 1929,92-101."},{"key":"14_CR56_14","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, Theoretical Computer Science 6 (1978), 223-231.","journal-title":"Theoretical Computer Science"},{"key":"14_CR57_14","volume-title":"Analysis of asynchronous concurrent systems by timed Petri nets","author":"C. Ramchandani","year":"1974","unstructured":"C. Ramchandani. Analysis of asynchronous concurrent systems by timed Petri nets, PhD thesis, MIT, Boston, 1974"},{"key":"14_CR58_14","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 New York, Inc., New York, NY, 1985."},{"issue":"1","key":"14_CR59_14","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0022-0000(86)90006-1","volume":"32","author":"L. Rosier","year":"1986","unstructured":"L. Rosier and H. Yen. A multiparameter analysis of the boundedness problem for vector addition systems, Journal of Computer and System Sciences 32, 1 (1986),105-135.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR60_14","doi-asserted-by":"crossref","unstructured":"G. Sacerdote and R. Tenney. The decidability of the reachability problem for vector addition systems, STOC, 1977, 61-76.","DOI":"10.1145\/800105.803396"},{"key":"14_CR61_14","doi-asserted-by":"crossref","unstructured":"J. van Leeuwen. A partial solution to the reachability problem for vector addition systems, STOC, 1974, 303-309.","DOI":"10.1145\/800119.803908"},{"key":"14_CR62_14","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, Theoretical Computer Science 31 (1984), 307-315.","journal-title":"Theoretical Computer Science"},{"key":"14_CR63_14","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1006\/inco.1996.0013","volume":"2","author":"H. Yen","year":"1996","unstructured":"H. Yen. On the regularity of Petri net languages, Information and Computation 124,2 (1996),168-181.","journal-title":"Information and Computation 124"},{"key":"14_CR64_14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0304-3975(96)00147-8","volume":"179","author":"H. Yen","year":"1997","unstructured":"H. Yen. On reachability equivalence for BPP-nets, Theoretical Computer Science 179 (1997),301-317.","journal-title":"Theoretical Computer Science"}],"container-title":["Studies in Computational Intelligence","Recent Advances in Formal Languages and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-33461-3_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:37:43Z","timestamp":1605760663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-33461-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540334606","9783540334613"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-33461-3_14","relation":{},"ISSN":["1860-949X","1860-9503"],"issn-type":[{"type":"print","value":"1860-949X"},{"type":"electronic","value":"1860-9503"}],"subject":[],"published":{"date-parts":[[2006]]}}}