{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:40:51Z","timestamp":1725468051729},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540638766"},{"type":"electronic","value":"9783540696599"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0058039","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T10:48:04Z","timestamp":1154602084000},"page":"312-326","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial-Time Many-One reductions for Petri nets"],"prefix":"10.1007","author":[{"given":"Catherine","family":"Dufourd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Finkel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"issue":"1","key":"22_CR1","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(76)90067-0","volume":"3","author":"T. Araki","year":"1977","unstructured":"T. Araki and T. Kasami. Some decision problems related to the reachability problem for Petri nets. TCS, 3(1):85\u2013104, 1977.","journal-title":"TCS"},{"key":"22_CR2","volume-title":"PhD thesis","author":"Z. Bouziane","year":"1996","unstructured":"Z. Bouziane. Algorithmes primitifs r\u00e9cursifs et probl\u00e8mes\n                Expspace-complets pour les r\u00e9seaux de Petri cycliques. PhD thesis, LSV, \u00e9cole Normale Sup\u00e9rieure de Cachan, France, November 1996."},{"doi-asserted-by":"crossref","unstructured":"E. Cardoza, R. Lipton, and A. Meyer. Exponential space complete problems for Petri nets and commutative semigroups. In Proc. of the 8th annual ACM Symposium on theory of computing, pages 50\u201354, May 1976.","key":"22_CR3","DOI":"10.1145\/800113.803630"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0304-3975(94)00231-7","volume":"147","author":"A. Cheng","year":"1995","unstructured":"A. Cheng, J. Esparza, and J. Palsberg. Complexity result for 1-safe nets. TCS, 147:117\u2013136, 1995.","journal-title":"TCS"},{"doi-asserted-by":"crossref","unstructured":"J. Desel and J. Esparza. Free Choice Petri Nets. Cambridge University Press, 1995.","key":"22_CR5","DOI":"10.1017\/CBO9780511526558"},{"unstructured":"C. Dufourd and A. Finkel. A polynomial \u03bb-bisimilar normalization for Petri nets. Technical report, LIFAC, ENS de Cachan, July 1996. Presented at AFL'96, Salg\u00f3tarj\u00e1n, Hungary, 1996.","key":"22_CR6"},{"key":"22_CR7","first-page":"254","volume":"52","author":"J. Esparza","year":"1994","unstructured":"J. Esparza and M. Nielsen. Decidability issues on Petri nets \u2014 a survey. Bulletin of the EATCS, 52:254\u2013262, 1994.","journal-title":"Bulletin of the EATCS"},{"unstructured":"M. Hack. Decidability questions for Petri Nets. PhD thesis, M.I.T., 1976.","key":"22_CR8"},{"unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 1979.","key":"22_CR9"},{"doi-asserted-by":"crossref","unstructured":"M. Jantzen. Complexity of Place\/Transition nets. In Petri nets: central models and their properties, volume 254 of LNCS, pages 413\u2013434. Springer-Verlag, 1986.","key":"22_CR10","DOI":"10.1007\/978-3-540-47919-2_16"},{"key":"22_CR11","first-page":"146","volume":"3","author":"R.M. Karp","year":"1969","unstructured":"R.M. Karp and R.E. Miller. Parallel program schemata. Journal of Computer and System Sciences, 3:146\u2013195, 1969.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"R. Kosaraju. Decidability of reachability in vector addition systems. In Proc. of the 14th Annual ACM Symposium on Theory of Computing, San Francisco, pages 267\u2013281, May 1982.","key":"22_CR12","DOI":"10.1145\/800070.802201"},{"unstructured":"R.J. Lipton. The reachability problem requires exponential space. Technical Report 62, Yale University, Department of computer science, January 1976.","key":"22_CR13"},{"issue":"3","key":"22_CR14","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1137\/0213029","volume":"13","author":"E.W. Mayr","year":"1984","unstructured":"E.W. Mayr. An algorithm for the general Petri net reachability problem. SIAM Journal on Computing, 13(3):441\u2013460, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E.W. Mayr","year":"1982","unstructured":"E.W. Mayr and R. Meyer. The complexity of the word problem for commutative semigroups and polynomial ideals. Advances in Mathematics, 46:305\u2013329, 1982.","journal-title":"Advances in Mathematics"},{"unstructured":"J.L. Peterson. Petri Net Theory and the Modeling of Systems. Prentice Hall, 1981.","key":"22_CR16"},{"doi-asserted-by":"crossref","unstructured":"C. Rackoff. The covering and boundedness problems for vector addition systems. TCS, 6(2), 1978.","key":"22_CR17","DOI":"10.1016\/0304-3975(78)90036-1"},{"doi-asserted-by":"crossref","unstructured":"R. Valk. Self-modifying nets, a natural extension of Petri nets. In Proc. of ICALP'78, volume 62 of LNCS, pages 464\u2013476. Springer-Verlag, September 1978.","key":"22_CR18","DOI":"10.1007\/3-540-08860-1_35"},{"doi-asserted-by":"crossref","unstructured":"R. Valk. Generalizations of Petri nets. In Proc. of the 10th Symposium on Mathematical Fondations of Computer Science, volume 118 of LNCS, pages 140\u2013155. Springer-Verlag, 1981.","key":"22_CR19","DOI":"10.1007\/3-540-10856-4_80"},{"issue":"3","key":"22_CR20","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. Journal of Computer and System Sciences, 23(3):299\u2013325, 1981.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0058039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T13:19:18Z","timestamp":1558271958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0058039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540638766","9783540696599"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0058039","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"13 July 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}