{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:10:57Z","timestamp":1725459057267},"publisher-location":"Berlin\/Heidelberg","reference-count":27,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540156895"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028820","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T12:15:07Z","timestamp":1138191307000},"page":"361-370","source":"Crossref","is-referenced-by-count":0,"title":["A multiparameter analysis of the boundedness problem for vector addition systems"],"prefix":"10.1007","author":[{"given":"Louis E.","family":"Rosier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsu-Chun","family":"Yen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"36_CR1","first-page":"81","volume-title":"Proceedings of the First Annual Symposium on Computer Architecture","author":"T. Agerwala","year":"1973","unstructured":"Agerwala, T. and Flynn, M., Comments on Capabilities, Limitations, and \u2018Correctness\u2019 of Petri Nets, Proceedings of the First Annual Symposium on Computer Architecture, New York: ACM, 1973, pp. 81\u201386."},{"issue":"2","key":"36_CR2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1090\/S0002-9939-1976-0396605-3","volume":"55","author":"I. Borosh","year":"1976","unstructured":"Borosh, I. and Treybis, L., Bounds on Positive Integral Solutions of Linear Diophantine Equations, Proc. AMS, Vol. 55, No. 2, pp. 299\u2013304, March 1976.","journal-title":"Proc. AMS"},{"issue":"1","key":"36_CR3","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. Cook","year":"1971","unstructured":"Cook, S., Characterizations of Pushdown Machines in Terms of Time Bounded Computers, J. ACM, Vol. 18, No. 1, January 1971, pp. 4\u201318.","journal-title":"J. ACM"},{"key":"36_CR4","unstructured":"Cunha, P. and Maibaum, T., A Synchronous Calculus for Message Oriented Programming, Proceedings of the Second International Conference on Distributed Computing Systems, April 1981, pp. 443\u2013445."},{"key":"36_CR5","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 and Company, San Francisco, 1979."},{"key":"36_CR6","unstructured":"Gouda, M., Gurari, E., Lai, T. and Rosier, L., Deadlock Detection in Systems of Communicating Finite State Machines, Tech. Rep. No. 84-11, University of Texas at Austin, Department of Computer Sciences, April 1984."},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"Gouda, M. and Rosier, L., Priority Networks of Communicating Finite State Machines, to appear in SIAM Journal on Computing, Vol. 14, No. 3, August 1985.","DOI":"10.1137\/0214042"},{"issue":"4","key":"36_CR8","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/1008939.1008947","volume":"15","author":"E. Gurari","year":"1984","unstructured":"Gurari, E. and Lai, T., Deadlock Detection in Communicating Finite State Machines, ACM SIGACT NEWS, Vol. 15, No. 4, and Vol. 16, No. 1, Winter\u2013Spring 1984, pp. 63\u201364.","journal-title":"ACM SIGACT NEWS"},{"key":"36_CR9","unstructured":"Hack, M., Decidability Questions for Petri Nets, M.I.T., LCS, TR. 161, June 1976."},{"key":"36_CR10","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., Vol. 8, 1979, pp. 135\u2013159.","journal-title":"Theoret. Comp. Sci."},{"key":"36_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J. and Ullman, J., \"Introduction to Automata Theory, Languages, and Computation\", Addison-Wesley, Reading, Mass., 1979."},{"key":"36_CR12","first-page":"277","volume":"8","author":"N. Jones","year":"1979","unstructured":"Jones, N., Landweber, L. and Lien, Y., Complexity of Some Problems in Petri Nets, Theoret. Comp. Sci., Vol. 8, 1979, pp. 277\u2013299.","journal-title":"Theoret. Comp. Sci."},{"key":"36_CR13","unstructured":"Kasai, T. and Iwata, S., Gradually Intractable Problems and Nondeterministic Log-Space Lower Bounds, to appear in Math. Systems Theory."},{"issue":"2","key":"36_CR14","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(69)80011-5","volume":"3","author":"R. Karp","year":"1969","unstructured":"Karp, R. and Miller, R., Parallel Program Schemata, J. Computer and System Sciences, Vol. 3, No. 2, 1969, pp. 147\u2013195.","journal-title":"J. Computer and System Sciences"},{"issue":"4","key":"36_CR15","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1145\/957195.808062","volume":"7","author":"S. Kosaraju","year":"1973","unstructured":"Kosaraju, S., Limitations of Dijkstra's Semaphore Primitives and Petri Nets, Operating Systems Review, Vol. 7, No. 4, Oct. 1973, pp. 122\u2013126.","journal-title":"Operating Systems Review"},{"key":"36_CR16","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. Lawler","year":"1976","unstructured":"Lawler, E., \"Combinatorial Optimization: Networks and Matroids\", Holt, Rinehart and Winston, New York, 1976."},{"key":"36_CR17","unstructured":"Lipton, R., The Reachability Problem Requires Exponential Space, Yale University, Dept. of CS., Report No. 62, Jan., 1976."},{"key":"36_CR18","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E. Mayr","year":"1982","unstructured":"Mayr, E. and Meyer, A., The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals, Advances in Mathematics, 46, 1982, pp. 305\u2013329.","journal-title":"Advances in Mathematics"},{"key":"36_CR19","volume-title":"Computation: Finite and Infinite Machines","author":"M. Minsky","year":"1967","unstructured":"Minsky, M., \"Computation: Finite and Infinite Machines\", Prentice Hall, Englewood Cliffs, NJ, 1967."},{"issue":"3","key":"36_CR20","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1145\/360680.360709","volume":"18","author":"D. Parnas","year":"1975","unstructured":"Parnas, D., On a Solution to the Cigarette Smoker's Problem (Without Conditional Statements), Communications of the ACM, Vol. 18, No. 3, March 1975, pp. 181\u2013183.","journal-title":"Communications of the ACM"},{"key":"36_CR21","unstructured":"Patil, S., Limitations and Capabilities of Dijkstra's Semaphore Primitives for Coordination Among Processes, Group Memo 57, Project MAC, MIT, February 1971."},{"key":"36_CR22","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":"36_CR23","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., Vol. 6, 1978, pp. 223\u2013231.","journal-title":"Theoret. Comp. Sci."},{"key":"36_CR24","unstructured":"Rosier, L. and Gouda, M., On Deciding Progress for a Class of Communication Protocols, Proceedings of the Eighteen Annual Conference on Information Science and Systems, Princeton Univ., 1984, pp. 663\u2013667."},{"key":"36_CR25","doi-asserted-by":"crossref","unstructured":"Rosier, L. and Yen, H., Boundedness, Empty Channel Detection and Synchronization for Communicating Finite State Machines, Proceedings of the Second Annual Symposium on Theoretical Aspects of Computer Science, Saarbrucken, West-Germany, 1985, pp. 287\u2013298.","DOI":"10.1007\/BFb0024017"},{"issue":"2","key":"36_CR26","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"Savitch, W., Relationships between Nondeterministic and Deterministic Tape Complexities, J. of Computer and System Sciences, Vol. 4, No. 2, 1970, pp. 177\u2013192.","journal-title":"J. of Computer and System Sciences"},{"key":"36_CR27","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0020-0190(83)90105-9","volume":"17","author":"Y. Yu","year":"1983","unstructured":"Yu, Y. and Gouda, M., Unboundedness Detection for a Class of Communicating Finite State Machines, Information Processing Letters, Vol. 17, December 1983, pp. 235\u2013240.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028820.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:59:09Z","timestamp":1607533149000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540156895"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0028820","relation":{},"subject":[]}}