{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T18:02:24Z","timestamp":1784484144608,"version":"3.55.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032313478","type":"print"},{"value":"9783032313485","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2027]]},"DOI":"10.1007\/978-3-032-31348-5_30","type":"book-chapter","created":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:08Z","timestamp":1784482148000},"page":"453-468","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Safety and\u00a0Reachability in\u00a0k-Control Games on\u00a0Integer Vector Addition Systems with\u00a0States"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2210-1481","authenticated-orcid":false,"given":"Reino","family":"Niskanen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7192-7853","authenticated-orcid":false,"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Topley","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,20]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., Bouajjani, A., d\u2019Orso, J.: Deciding monotonic games. In: Baaz, M., Makowsky, J.A. (eds.) Computer Science Logic. CSL 2003. LNCS, vol. 2803, pp. 1\u201314. Springer, Berlin, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45220-1_1","DOI":"10.1007\/978-3-540-45220-1_1"},{"key":"30_CR2","doi-asserted-by":"publisher","unstructured":"Arul, A., \u00a0Reichert, J.: The complexity of robot games on the integer line. In: Proceedings of QAPL 2013, volume 117 of EPTCS, pp. 132\u2013148, 2013. https:\/\/doi.org\/10.4204\/EPTCS.117.9","DOI":"10.4204\/EPTCS.117.9"},{"key":"30_CR3","doi-asserted-by":"publisher","unstructured":"Blondin, M., Finkel, A., G\u00f6ller, S., Haase, C., McKenzie, P.: Reachability in two-dimensional vector addition systems with states is PSPACE-complete. In: Proceedings of LICS 2015, pp. 32\u201343, 2015. https:\/\/doi.org\/10.1109\/LICS.2015.14","DOI":"10.1109\/LICS.2015.14"},{"key":"30_CR4","doi-asserted-by":"publisher","unstructured":"Br\u00e1zdil, T., \u00a0Jan\u010dar, P., \u00a0Ku\u010dera, A.: Reachability games on extended vector addition systems with states. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) Automata, Languages and Programming. ICALP 2010. LNCS, vol. 6199, pp. 478\u2013489. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14162-1_40","DOI":"10.1007\/978-3-642-14162-1_40"},{"key":"30_CR5","doi-asserted-by":"publisher","unstructured":"Chistikov, D., \u00a0Haase, C., \u00a0Halfon, S.: Context-free commutative grammars with integer counters and resets. Theor. Comput. Sci. 735, 147\u2013161 (2018). https:\/\/doi.org\/10.1016\/J.TCS.2016.06.017","DOI":"10.1016\/J.TCS.2016.06.017"},{"key":"30_CR6","doi-asserted-by":"publisher","unstructured":"Chonev, V., \u00a0Ouaknine, J., \u00a0Worrell, J.: The polyhedron-hitting problem. In: Proceedings of SODA 2015, pp. 940\u2013956. SIAM, 2015. https:\/\/doi.org\/10.1137\/1.9781611973730.64","DOI":"10.1137\/1.9781611973730.64"},{"key":"30_CR7","doi-asserted-by":"publisher","unstructured":"Chonev, V., \u00a0Ouaknine, J.,\u00a0Worrell, J.: On the complexity of the orbit problem. J. ACM 63(3), 23:1\u201323:18 (2016). https:\/\/doi.org\/10.1145\/2857050","DOI":"10.1145\/2857050"},{"key":"30_CR8","doi-asserted-by":"publisher","unstructured":"Czerwi\u0144ski, W., \u00a0Jecker, I., \u00a0Lasota, S., \u00a0Leroux, J., \u00a0Orlikowski, L.: New lower bounds for reachability in vector addition systems. In: Proceedings of FSTTCS 2023, volume 284 of LIPIcs, pp. 35:1\u201335:22. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2023. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2023.35","DOI":"10.4230\/LIPIcs.FSTTCS.2023.35"},{"key":"30_CR9","doi-asserted-by":"publisher","unstructured":"Czerwinski, W., \u00a0Orlikowski, L.: Reachability in vector addition systems is ackermann-complete. In: Proceedings of FOCS 2022, pp. 1229\u20131240. IEEE, 2021. https:\/\/doi.org\/10.1109\/FOCS52979.2021.00120","DOI":"10.1109\/FOCS52979.2021.00120"},{"key":"30_CR10","unstructured":"Doyen, L., \u00a0Rabinovich, A.: Robot games. Technical Report LSV-13-02, LSV, ENS Cachan, 2013. http:\/\/www.lsv.fr\/Publis\/RAPPORTS_LSV\/PDF\/rr-lsv-2013-02.pdf"},{"key":"30_CR11","doi-asserted-by":"publisher","unstructured":"Dufourd, C., \u00a0Finkel, A., \u00a0Schnoebelen, P.: Reset nets between decidability and undecidability. In: Proceedings of ICALP 1998, volume 1443 of LNCS, pp. 103\u2013115. Springer, Cham (1998). https:\/\/doi.org\/10.1007\/bfb0055044","DOI":"10.1007\/bfb0055044"},{"key":"30_CR12","doi-asserted-by":"publisher","unstructured":"Englert, M., \u00a0Lazi\u0107, R., \u00a0Totzke, P.: Reachability in two-dimensional unary vector addition systems with states is NL-complete. In: Proceedings of LICS, pp. 477\u2013484. ACM, 2016. https:\/\/doi.org\/10.1145\/2933575.2933577","DOI":"10.1145\/2933575.2933577"},{"key":"30_CR13","doi-asserted-by":"publisher","unstructured":"Figueira, D., \u00a0Lazi\u0107, R., \u00a0Leroux, J.F., \u00a0Sutre, G.: Polynomial-space completeness of reachability for succinct branching VASS in dimension one. In: Proceedings of ICALP 2017, vol. 80, pp. 119:1\u2013119:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2017. https:\/\/doi.org\/10.4230\/lipics.icalp.2017.119","DOI":"10.4230\/lipics.icalp.2017.119"},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"Fijalkow, N. (ed.): Games on Graphs: From Logic and Automata to Algorithms, 2025. arXiv:2305.10546","DOI":"10.1017\/9781009500678"},{"key":"30_CR15","doi-asserted-by":"publisher","unstructured":"Finkel, A., \u00a0G\u00f6ller, S., \u00a0Haase, C.: Reachability in register machines with polynomial updates. In: Chatterjee, K., Sgall, J. (eds.) Mathematical Foundations of Computer Science 2013. MFCS 2013. LNCS, vol. 8087, pp. 409\u2013420. Springer, Berlin, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40313-2_37","DOI":"10.1007\/978-3-642-40313-2_37"},{"key":"30_CR16","doi-asserted-by":"publisher","unstructured":"Fischer, M.J., Rabin, M.O.: Super-exponential complexity of Presburger arithmetic. In: Complexity of Computation, SIAM-AMS Proceedings, vol. 7, pp. 27\u201341. SIAM, 1974. https:\/\/doi.org\/10.1007\/978-3-7091-9459-1_5","DOI":"10.1007\/978-3-7091-9459-1_5"},{"key":"30_CR17","doi-asserted-by":"publisher","unstructured":"Gr\u00e4del, E., \u00a0Thomas, W., \u00a0Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research, LNCS, vol. 2500. Springer, Cham (2002). https:\/\/doi.org\/10.1007\/3-540-36387-4","DOI":"10.1007\/3-540-36387-4"},{"key":"30_CR18","doi-asserted-by":"publisher","unstructured":"Haase, C., \u00a0Kreutzer, S., \u00a0Ouaknine, J.,\u00a0Worrell, J.: Reachability in succinct and parametric one-counter automata. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009 - Concurrency Theory. CONCUR 2009. LNCS, vol. 5710, pp. 369\u2013383. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04081-8_25","DOI":"10.1007\/978-3-642-04081-8_25"},{"key":"30_CR19","doi-asserted-by":"publisher","unstructured":"Hopcroft, J.E., Pansiot, J.-J.: On the reachability problem for 5-dimensional vector addition systems. Theor. Comput. Sci. 8, 135\u2013159 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90041-0","DOI":"10.1016\/0304-3975(79)90041-0"},{"key":"30_CR20","doi-asserted-by":"publisher","unstructured":"Hunter, P.: Reachability in succinct one-counter games. In: Bojanczyk, M., Lasota, S., Potapov, I. (eds.) Reachability Problems. RP 2015. LNCS, vol. 9328, pp. 37\u201349. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24537-9_5","DOI":"10.1007\/978-3-319-24537-9_5"},{"key":"30_CR21","doi-asserted-by":"publisher","unstructured":"Karp, R.,\u00a0Miller, R.: Parallel program schemata. J. Comput. Syst. Sci. 3(2), 147\u2013195 (1969). https:\/\/doi.org\/10.1016\/S0022-0000(69)80011-5","DOI":"10.1016\/S0022-0000(69)80011-5"},{"key":"30_CR22","doi-asserted-by":"publisher","unstructured":"Kosaraju, S.R.: Decidability of reachability in vector addition systems (preliminary version). In: Proceedings of STOC, pp. 267\u2013281. ACM, 1982. https:\/\/doi.org\/10.1145\/800070.802201","DOI":"10.1145\/800070.802201"},{"key":"30_CR23","doi-asserted-by":"publisher","unstructured":"Lambert, J.L.: A structure to decide reachability in Petri nets. Theor. Comput. Sci. 99(1), 79\u2013104 (1992). https:\/\/doi.org\/10.1016\/0304-3975(92)90173-d","DOI":"10.1016\/0304-3975(92)90173-d"},{"key":"30_CR24","doi-asserted-by":"publisher","unstructured":"Lazi\u0107, R.: The reachability problem for branching vector addition systems requires doubly-exponential space. Inf. Process. Lett. 110(17), 740\u2013745 (2010). https:\/\/doi.org\/10.1016\/j.ipl.2010.06.008","DOI":"10.1016\/j.ipl.2010.06.008"},{"key":"30_CR25","doi-asserted-by":"publisher","unstructured":"Leroux, J.: The reachability problem for petri nets is not primitive recursive. In: Proceedings of FOCS, pp. 1241\u20131252, 2022. https:\/\/doi.org\/10.1109\/FOCS52979.2021.00121","DOI":"10.1109\/FOCS52979.2021.00121"},{"key":"30_CR26","doi-asserted-by":"publisher","unstructured":"Leroux, J., \u00a0Schmitz, S.: Demystifying reachability in vector addition systems. In: Proceedings of LICS 2015, pp. 56\u201367. IEEE, 2015. https:\/\/doi.org\/10.1109\/LICS.2015.16","DOI":"10.1109\/LICS.2015.16"},{"key":"30_CR27","unstructured":"Lipton, R.: The reachability problem requires exponential space. Technical report, Department of Computer Science, Yale University, 1976"},{"key":"30_CR28","doi-asserted-by":"publisher","unstructured":"Mayr, E.: An algorithm for the general Petri net reachability problem. In: Proceedings of STOC 1981, pp. 238\u2013246. ACM, 1981. https:\/\/doi.org\/10.1145\/800076.802477","DOI":"10.1145\/800076.802477"},{"key":"30_CR29","unstructured":"Niskanen, R.: Reachability games and related matrix and word problems. PhD thesis, University of Liverpool, UK, 2018. https:\/\/livrepository.liverpool.ac.uk\/3018108\/"},{"key":"30_CR30","doi-asserted-by":"publisher","unstructured":"Niskanen, R., \u00a0Potapov, I., \u00a0Reichert, J.: On decidability and complexity of low-dimensional robot games. J. Comput. Syst. Sci. 107, 124\u2013141 (2020). https:\/\/doi.org\/10.1016\/J.JCSS.2019.08.003","DOI":"10.1016\/J.JCSS.2019.08.003"},{"key":"30_CR31","unstructured":"Petri, C.: Fundamentals of a theory of asynchronous information flow. In: IFIP Congress 1962, pp. 386\u2013390, 1962"},{"key":"30_CR32","doi-asserted-by":"publisher","unstructured":"Rackoff, C.: The covering and boundedness problems for vector addition systems. Theor. Comput. Sci. 6(2), 223\u2013231 (1978). https:\/\/doi.org\/10.1016\/0304-3975(78)90036-1","DOI":"10.1016\/0304-3975(78)90036-1"},{"key":"30_CR33","unstructured":"Reichert, J.: Reachability games with counters: decidability and algorithms. Doctoral thesis, LSV, ENS Cachan, France, 2015"},{"key":"30_CR34","doi-asserted-by":"publisher","unstructured":"Reichert, J.: On the complexity of counter reachability games. Fundam. Inform. 143(3-4), 415\u2013436 (2016). https:\/\/doi.org\/10.3233\/FI-2016-1320","DOI":"10.3233\/FI-2016-1320"},{"key":"30_CR35","doi-asserted-by":"publisher","unstructured":"Rosier, L., Yen, H.-S.: A multiparameter analysis of the boundedness problem for vector addition systems. J. Comput. Syst. Sci. 32(1), 105\u2013135 (1986). https:\/\/doi.org\/10.1016\/0022-0000(86)90006-1","DOI":"10.1016\/0022-0000(86)90006-1"},{"key":"30_CR36","doi-asserted-by":"publisher","unstructured":"Valiant, L.G., \u00a0Paterson, M.: Deterministic one-counter automata. J. Comput. Syst. Sci. 10(3), 340\u2013350 (1975). https:\/\/doi.org\/10.1016\/S0022-0000(75)80005-5","DOI":"10.1016\/S0022-0000(75)80005-5"}],"container-title":["Lecture Notes in Computer Science","Timeless Machines: Computability Across Eras"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31348-5_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:29:09Z","timestamp":1784482149000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31348-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,20]]},"ISBN":["9783032313478","9783032313485"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31348-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,20]]},"assertion":[{"value":"20 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}