{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T18:20:14Z","timestamp":1784830814997,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642207112","type":"print"},{"value":"9783642207129","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-20712-9_7","type":"book-chapter","created":{"date-parts":[[2011,6,11]],"date-time":"2011-06-11T00:05:22Z","timestamp":1307750722000},"page":"77-90","source":"Crossref","is-referenced-by-count":10,"title":["The Complexity of Solving Reachability Games Using Value and Strategy Iteration"],"prefix":"10.1007","author":[{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"7_CR1","first-page":"291","volume-title":"Third International Conference on the Quantitative Evaluation of Systems","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, pp. 291\u2013300. IEEE Press, New York (2006)"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1137\/1.9781611973068.23","volume-title":"20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"K. Chatterjee","year":"2009","unstructured":"Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Termination criteria for solving concurrent safety and reachability games. In: 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 197\u2013206. SIAM, Philadelphia (2009)"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-540-30124-0_6","volume-title":"Computer Science Logic","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.\u00a03210, pp. 26\u201340. Springer, Heidelberg (2004)"},{"key":"7_CR4","doi-asserted-by":"crossref","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)","DOI":"10.1090\/dimacs\/013\/04"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1014\u20131023. Springer, Heidelberg (2009)"},{"key":"7_CR6","doi-asserted-by":"publisher","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.\u00a0386, 188\u2013217 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/11787006_28","volume-title":"Automata, Languages and Programming","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 2006. LNCS, vol.\u00a04052, pp. 324\u2013335. Springer, Heidelberg (2006)"},{"key":"7_CR8","series-title":"Annals of Mathematical Studies","first-page":"47","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.\u00a039, pp. 47\u201378. Princeton University Press, Princeton (1957)"},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/LICS.2009.27","volume-title":"24th Annual IEEE Symposium on Logic in Computer Science","author":"O. Friedmann","year":"2009","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: 24th Annual IEEE Symposium on Logic in Computer Science, pp. 145\u2013156. IEEE Press, New York (2009)"},{"key":"7_CR10","unstructured":"Hansen, K.A., Ibsen-Jensen, R., Miltersen, P.B.: The complexity of solving reachability games using value and strategy iteration, \n                  \n                    http:\/\/arxiv.org\/abs\/1007.1812"},{"key":"7_CR11","volume-title":"43rd ACM Symposium on Theory of Computing","author":"K.A. Hansen","year":"2011","unstructured":"Hansen, K.A., Kouck\u00fd, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.: Exact Algorithms for Solving Stochastic Games. In: 43rd ACM Symposium on Theory of Computing, ACM Press, New York (2011)"},{"key":"7_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","author":"K.A. Hansen","year":"2009","unstructured":"Hansen, K.A., Kouck\u00fd, M., Miltersen, P.B.: Winning concurrent reachability games requires doubly exponential patience. In: 24th Annual IEEE Symposium on Logic in Computer Science, pp. 332\u2013341. IEEE Press, New York (2009)"},{"key":"7_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. Amer. Math. Soc.\u00a060, 245\u2013251 (1976)","journal-title":"Proc. Amer. Math. Soc."},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1287\/mnsc.12.5.359","volume":"12","author":"A. Hoffman","year":"1966","unstructured":"Hoffman, A., Karp, R.: On nonterminating stochastic games. Management Science\u00a012, 359\u2013370 (1966)","journal-title":"Management Science"},{"key":"7_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":"7_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01769259","volume":"10","author":"J.F. Mertens","year":"1981","unstructured":"Mertens, J.F., Neyman, A.: Stochastic games. International Journal of Game Theory\u00a010, 53\u201366 (1981)","journal-title":"International Journal of Game Theory"},{"key":"7_CR17","doi-asserted-by":"publisher","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. Amer. Math. Soc.\u00a077, 134\u2013136 (1971)","journal-title":"Bull. Amer. Math. Soc."},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/BF00935562","volume":"11","author":"S. Rao","year":"1973","unstructured":"Rao, S., Chandrasekaran, R., Nair, K.: Algorithms for discounted games. J. Optimiz. Theory App.\u00a011, 627\u2013637 (1973)","journal-title":"J. Optimiz. Theory App."},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"L.S.. Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences, U.S.A.\u00a039, 1095\u20131100 (1953)","journal-title":"Proceedings of the National Academy of Sciences, U.S.A."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20712-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T19:58:10Z","timestamp":1548446290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20712-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642207112","9783642207129"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20712-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}