{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T07:06:41Z","timestamp":1777619201101,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,12,6]],"date-time":"2013-12-06T00:00:00Z","timestamp":1386288000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s00224-013-9524-6","type":"journal-article","created":{"date-parts":[[2013,12,5]],"date-time":"2013-12-05T07:53:30Z","timestamp":1386230010000},"page":"380-403","source":"Crossref","is-referenced-by-count":8,"title":["The Complexity of Solving Reachability Games Using Value and Strategy Iteration"],"prefix":"10.1007","volume":"55","author":[{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,12,6]]},"reference":[{"issue":"3","key":"9524_CR1","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.tcs.2007.07.008","volume":"386","author":"L. Alfaro de","year":"2007","unstructured":"de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. Theor. Comput. Sci. 386(3), 188\u2013217 (2007). doi: 10.1016\/j.tcs.2007.07.008","journal-title":"Theor. Comput. Sci."},{"key":"9524_CR2","first-page":"291","volume-title":"Third International Conference on the Quantitative Evaluation of Systems. QEST\u201906","author":"K. Chatterjee","year":"2006","unstructured":"Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Strategy improvement for concurrent reachability games. In: Third International Conference on the Quantitative Evaluation of Systems. QEST\u201906, pp. 291\u2013300. IEEE Computer Society, New York (2006)"},{"key":"9524_CR3","volume-title":"Proceedings of the Twenteeth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909)","author":"K. Chatterjee","year":"2009","unstructured":"Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Termination criteria for solving concurrent safety and reachability games. In: Proceedings of the Twenteeth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909) (2009)"},{"key":"9524_CR4","series-title":"LNCS","first-page":"26","volume-title":"CSL 2004","author":"K. Chatterjee","year":"2004","unstructured":"Chatterjee, K., Majumdar, R., Jurdzi\u0144ski, M.: On Nash equilibria in stochastic games. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 26\u201340. Springer, Berlin (2004)"},{"key":"9524_CR5","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1090\/dimacs\/013\/04","volume-title":"Advances in Computational Complexity Theory","author":"A. Condon","year":"1993","unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 51\u201373 (1993)"},{"key":"9524_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1007\/978-3-642-10631-6_102","volume-title":"Algorithms and Computation","author":"D. Dai","year":"2009","unstructured":"Dai, D., Ge, R.: New results on simple stochastic games. In: Algorithms and Computation 20th International Symposium, ISAAC Proceedings 2009, Honolulu, Hawaii, USA, December 16\u201318, 2009. Lecture Notes in Computer Science, vol. 5878, pp. 1014\u20131023. Springer, Berlin (2009)"},{"key":"9524_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/11787006_28","volume-title":"ICALP (2)","author":"K. Etessami","year":"2006","unstructured":"Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP (2). Lecture Notes in Computer Science, vol. 4052, pp. 324\u2013335. Springer, Berlin (2006)"},{"key":"9524_CR8","series-title":"Annals of Mathematical Studies","volume-title":"Contributions to the Theory of Games Vol. III","author":"H. Everett","year":"1957","unstructured":"Everett, H.: Recursive games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games Vol. III. Annals of Mathematical Studies, vol. 39. Princeton University Press, Princeton (1957)"},{"key":"9524_CR9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/LICS.2009.27","volume-title":"Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009","author":"O. Friedmann","year":"2009","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11\u201314 August 2009 Los Angeles, CA, USA, pp. 145\u2013156 (2009)"},{"key":"9524_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/978-3-642-20712-9_7","volume-title":"Computer Science\u2014Theory and Applications","author":"K.A. Hansen","year":"2011","unstructured":"Hansen, K.A., Ibsen-Jensen, R., Miltersen, P.B.: The complexity of solving reachability games using value and strategy iteration. In: Kulikov, A.S., Vereshchagin, N.K. (eds.) Computer Science\u2014Theory and Applications, Proceedings CSR 2011, St. Petersburg, Russia, June 14\u201318, 2011. Lecture Notes in Computer Science, vol. 6651, pp. 77\u201390. Springer, Berlin (2011)"},{"key":"9524_CR11","first-page":"205","volume-title":"STOC\u201911","author":"K.A. Hansen","year":"2011","unstructured":"Hansen, K.A., Kouck\u00fd, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.P.: Exact algorithms for solving discounted stochastic games and recursive games. In: STOC\u201911, pp. 205\u2013214. (2011)"},{"key":"9524_CR12","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1109\/LICS.2009.44","volume-title":"24th Annual IEEE Symposium on Logic in Computer Science (LICS\u201909)","author":"K.A. Hansen","year":"2009","unstructured":"Hansen, K.A., Koucky, M., Miltersen, P.B.: Winning concurrent reachability games requires doubly exponential patience. In: 24th Annual IEEE Symposium on Logic in Computer Science (LICS\u201909), pp. 332\u2013341. IEEE, New York (2009)"},{"key":"9524_CR13","first-page":"245","volume":"60","author":"C.J. Himmelberg","year":"1976","unstructured":"Himmelberg, C.J., Parthasarathy, T., Raghavan, T.E.S., Vleck, F.S.V.: Existence of p-equilibrium and optimal stationary strategies in stochastic games. Proc. Am. Math. Soc. 60, 245\u2013251 (1976)","journal-title":"Proc. Am. Math. Soc."},{"key":"9524_CR14","doi-asserted-by":"crossref","unstructured":"Hoffman, A., Karp, R.: On nonterminating stochastic games. Manag. Sci. 359\u2013370 (1966)","DOI":"10.1287\/mnsc.12.5.359"},{"key":"9524_CR15","volume-title":"Dynamic Programming and Markov Processes","author":"R. Howard","year":"1960","unstructured":"Howard, R.: Dynamic Programming and Markov Processes. MIT Press, Cambridge (1960)"},{"key":"9524_CR16","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01769259","volume":"10","author":"J.F. Mertens","year":"1981","unstructured":"Mertens, J.F., Neyman, A.: Stochastic games. Int. J. Game Theory 10, 53\u201366 (1981)","journal-title":"Int. J. Game Theory"},{"key":"9524_CR17","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1090\/S0002-9904-1971-12633-2","volume":"77","author":"T. Parthasarathy","year":"1971","unstructured":"Parthasarathy, T.: Discounted and positive stochastic games. Bull. Am. Math. Soc. 77, 134\u2013136 (1971)","journal-title":"Bull. Am. Math. Soc."},{"key":"9524_CR18","doi-asserted-by":"crossref","unstructured":"Rao, S., Chandrasekaran, R., Nair, K.: Algorithms for discounted games. J. Optim. Theory Appl. 627\u2013637 (1973)","DOI":"10.1007\/BF00935562"},{"key":"9524_CR19","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"L.S. Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. USA 39, 1095\u20131100 (1953)","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9524-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9524-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9524-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T12:57:35Z","timestamp":1564923455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9524-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,6]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["9524"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9524-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,6]]}}}