{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:50:33Z","timestamp":1764557433553,"version":"3.37.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319670881"},{"type":"electronic","value":"9783319670898"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-67089-8_10","type":"book-chapter","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T12:47:26Z","timestamp":1503578846000},"page":"132-143","source":"Crossref","is-referenced-by-count":1,"title":["Reachability Problem for Polynomial Iteration Is\u00a0PSPACE-complete"],"prefix":"10.1007","author":[{"given":"Reino","family":"Niskanen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,25]]},"reference":[{"issue":"1\u20132","key":"10_CR1","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 391(1\u20132), 3\u201313 (2008). http:\/\/dx.doi.org\/10.1016\/j.tcs.2007.10.025","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10_CR2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.3233\/COM-150032","volume":"4","author":"AM Ben-Amram","year":"2015","unstructured":"Ben-Amram, A.M.: Mortality of iterated piecewise affine functions over the integers: decidability and complexity. Computability 4(1), 19\u201356 (2015). https:\/\/doi.org\/10.3233\/COM-150032","journal-title":"Computability"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Bournez, O., Kurganskyy, O., Potapov, I.: Reachability problems for one-dimensional piecewise affine maps. Manuscript (2017)","DOI":"10.1142\/S0129054118410046"},{"key":"10_CR4","first-page":"54","volume":"12","author":"V Claus","year":"1980","unstructured":"Claus, V.: Some remarks on PCP $$(k)$$ and related problems. Bull. EATCS 12, 54\u201361 (1980)","journal-title":"Bull. EATCS"},{"issue":"1","key":"10_CR5","doi-asserted-by":"crossref","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. J. Symb. Comput. 27(1), 21\u201329 (1999). https:\/\/doi.org\/10.1006\/jsco.1998.0242","journal-title":"J. Symb. Comput."},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-642-40313-2_37","volume-title":"Mathematical Foundations of Computer Science 2013","author":"A Finkel","year":"2013","unstructured":"Finkel, A., G\u00f6ller, S., Haase, C.: Reachability in register machines with polynomial updates. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 409\u2013420. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40313-2_37"},{"issue":"5","key":"10_CR7","doi-asserted-by":"crossref","first-page":"931","DOI":"10.1142\/S0129054107005066","volume":"18","author":"V Halava","year":"2007","unstructured":"Halava, V., Harju, T., Hirvensalo, M.: Undecidability bounds for integer matrices using Claus instances. Int. J. Found. Comput. Sci. 18(5), 931\u2013948 (2007). http:\/\/doi.org\/10.1142\/s0129054107005066","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"10_CR8","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/s00236-007-0047-y","volume":"44","author":"V Halava","year":"2007","unstructured":"Halava, V., Hirvensalo, M.: Improved matrix pair undecidability results. Acta Inf. 44(3), 191\u2013205 (2007). http:\/\/dx.doi.org\/10.1007\/s00236-007-0047-y","journal-title":"Acta Inf."},{"issue":"2","key":"10_CR9","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0304-3975(94)90229-1","volume":"132","author":"P Koiran","year":"1994","unstructured":"Koiran, P., Cosnard, M., Garzon, M.H.: Computability with low-dimensional dynamical systems. Theor. Comput. Sci. 132(2), 113\u2013128 (1994). http:\/\/doi.org\/10.1016\/0304-3975(94)90229-1","journal-title":"Theor. Comput. Sci."},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-662-49192-8_29","volume-title":"SOFSEM 2016: Theory and Practice of Computer Science","author":"O Kurganskyy","year":"2016","unstructured":"Kurganskyy, O., Potapov, I.: Reachability problems for PAMs. In: Freivalds, R.M., Engels, G., Catania, B. (eds.) SOFSEM 2016. LNCS, vol. 9587, pp. 356\u2013368. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49192-8_29"},{"issue":"4","key":"10_CR11","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1142\/S0129054108006054","volume":"19","author":"O Kurganskyy","year":"2008","unstructured":"Kurganskyy, O., Potapov, I., Sancho-Caparrini, F.: Reachability problems in low-dimensional iterative maps. Int. J. Found. Comput. Sci. 19(4), 935\u2013951 (2008). https:\/\/doi.org\/10.1142\/S0129054108006054","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"10_CR12","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","volume":"7","author":"SY Kuroda","year":"1964","unstructured":"Kuroda, S.Y.: Classes of languages and linear-bounded automata. Inf. Control 7(2), 207\u2013223 (1964). http:\/\/doi.org\/10.1016\/s0019-9958(64)90120-2","journal-title":"Inf. Control"},{"issue":"2","key":"10_CR13","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0019-9958(63)90169-4","volume":"6","author":"PS Landweber","year":"1963","unstructured":"Landweber, P.S.: Three theorems on phrase structure grammars of type 1. Inf. Control 6(2), 131\u2013136 (1963). http:\/\/doi.org\/10.1016\/s0019-9958(63)90169-4","journal-title":"Inf. Control"},{"key":"10_CR14","unstructured":"Neary, T.: Undecidability in binary tag systems and the post correspondence problem for five pairs of words. In: STACS 2015. LIPIcs, pp. 649\u2013661 (2015). http:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.649"},{"key":"10_CR15","unstructured":"Reichert, J.: Reachability Games with Counters: Decidability and Algorithms. Doctoral thesis, Laboratoire Sp\u00e9cification et V\u00e9rification, ENS Cachan, France (2015)"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67089-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T05:21:59Z","timestamp":1602825719000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67089-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319670881","9783319670898"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67089-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}