{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T06:14:49Z","timestamp":1784528089532,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403125","type":"print"},{"value":"9783642403132","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_37","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T10:36:43Z","timestamp":1376649403000},"page":"409-420","source":"Crossref","is-referenced-by-count":14,"title":["Reachability in Register Machines with Polynomial Updates"],"prefix":"10.1007","author":[{"given":"Alain","family":"Finkel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"G\u00f6ller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Haase","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Babi\u0107, D., Cook, B., Hu, A.J., Rakamari\u0107, Z.: Proving termination of nonlinear command sequences. Formal Aspects of Computing, 1\u201315 (2012)","DOI":"10.1007\/s00165-012-0252-5"},{"issue":"1-2","key":"37_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2007.10.025","volume":"391","author":"P. Bell","year":"2008","unstructured":"Bell, P., Potapov, I.: On undecidability bounds for matrix decision problems. Theoretical Computer Science\u00a0391(1-2), 3\u201313 (2008)","journal-title":"Theoretical Computer Science"},{"key":"37_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-642-22993-0_16","volume-title":"Mathematical Foundations of Computer Science 2011","author":"R. Bonnet","year":"2011","unstructured":"Bonnet, R.: The reachability problem for vector addition system with one zero-test. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 145\u2013157. Springer, Heidelberg (2011)"},{"key":"37_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-540-30579-8_8","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"A.R. Bradley","year":"2005","unstructured":"Bradley, A.R., Manna, Z., Sipma, H.B.: Termination of polynomial programs. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol.\u00a03385, pp. 113\u2013129. Springer, Heidelberg (2005)"},{"issue":"1","key":"37_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jsco.1998.0242","volume":"27","author":"F. Cucker","year":"1999","unstructured":"Cucker, F., Koiran, P., Smale, S.: A polynomial time algorithm for Diophantine equations in one variable. Journal of Symbolic Computation\u00a027(1), 21\u201329 (1999)","journal-title":"Journal of Symbolic Computation"},{"key":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BFb0055044","volume-title":"Automata, Languages and Programming","author":"C. Dufourd","year":"1998","unstructured":"Dufourd, C., Finkel, A., Schnoebelen, P.: Reset nets between decidability and undecidability. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 103\u2013115. Springer, Heidelberg (1998)"},{"key":"37_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/978-3-642-39212-2_21","volume-title":"ICALP 2013","author":"J. Fearnley","year":"2013","unstructured":"Fearnley, J., Jurdzi\u0144ski, M.: Reachability in two-clock timed automata is PSPACE-complete. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol.\u00a07966, pp. 212\u2013223. Springer, Heidelberg (2013)"},{"issue":"1-2","key":"37_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2004.01.005","volume":"195","author":"A. Finkel","year":"2004","unstructured":"Finkel, A., McKenzie, P., Picaronny, C.: A well-structured framework for analysing Petri net extensions. Information and Computation\u00a0195(1-2), 1\u201329 (2004)","journal-title":"Information and Computation"},{"key":"37_CR9","unstructured":"Fremont, D.: The reachability problem for affine functions on the integers (2012), \n                  \n                    http:\/\/web.mit.edu\/~dfremont\/www\/reachability.pdf"},{"key":"37_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-28729-9_27","volume-title":"Foundations of Software Science and Computational Structures","author":"S. G\u00f6ller","year":"2012","unstructured":"G\u00f6ller, S., Haase, C., Ouaknine, J., Worrell, J.: Branching-time model checking of parametric one-counter automata. In: Birkedal, L. (ed.) FOSSACS 2012. LNCS, vol.\u00a07213, pp. 406\u2013420. Springer, Heidelberg (2012)"},{"key":"37_CR11","unstructured":"Haase, C.: On the Complexity of Model Checking Counter Automata. PhD thesis, University of Oxford, UK (2012)"},{"key":"37_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-04081-8_25","volume-title":"CONCUR 2009 - Concurrency Theory","author":"C. Haase","year":"2009","unstructured":"Haase, C., Kreutzer, S., Ouaknine, J., Worrell, J.: Reachability in succinct and parametric one-counter automata. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol.\u00a05710, pp. 369\u2013383. Springer, Heidelberg (2009)"},{"key":"37_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-33512-9_6","volume-title":"Reachability Problems","author":"C. Haase","year":"2012","unstructured":"Haase, C., Ouaknine, J., Worrell, J.: On the relationship between reachability problems in timed and counter automata. In: Finkel, A., Leroux, J., Potapov, I. (eds.) RP 2012. LNCS, vol.\u00a07550, pp. 54\u201365. Springer, Heidelberg (2012)"},{"issue":"4","key":"37_CR14","doi-asserted-by":"publisher","first-page":"292","DOI":"10.2307\/2687152","volume":"28","author":"H.P. Hirst","year":"1997","unstructured":"Hirst, H.P., Macey, W.T.: Bounding the roots of polynomials. The College Mathematics Journal\u00a028(4), 292\u2013295 (1997)","journal-title":"The College Mathematics Journal"},{"issue":"1","key":"37_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0304-3975(92)90173-D","volume":"99","author":"J.-L. Lambert","year":"1992","unstructured":"Lambert, J.-L.: A structure to decide reachability in petri nets. Theoretical Computer Science\u00a099(1), 79\u2013104 (1992)","journal-title":"Theoretical Computer Science"},{"key":"37_CR16","unstructured":"Lipton, R.: The reachability problem is exponential-space-hard. Technical report, Yale University, New Haven, CT (1976)"},{"key":"37_CR17","first-page":"238","volume-title":"Proc. STOC","author":"E.W. Mayr","year":"1981","unstructured":"Mayr, E.W.: An algorithm for the general Petri net reachability problem. In: Proc. STOC, pp. 238\u2013246. ACM, New York (1981)"},{"issue":"3","key":"37_CR18","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M.L. Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive Unsolvability of Post\u2019s Problem of \u201cTag\u201d and other Topics in Theory of Turing Machines. The Annals of Mathematics\u00a074(3), 437\u2013455 (1961)","journal-title":"The Annals of Mathematics"},{"key":"37_CR19","unstructured":"Reichert, J.: Personal communication (2013)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:58:26Z","timestamp":1558015106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}