{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T16:43:10Z","timestamp":1772296990297,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642330896","type":"print"},{"value":"9783642330902","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_55","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"636-647","source":"Crossref","is-referenced-by-count":7,"title":["Solving Simple Stochastic Games with Few Coin Toss Positions"],"prefix":"10.1007","author":[{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"first","affiliation":[]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-69407-6_1","volume-title":"Logic and Theory of Algorithms","author":"D. Andersson","year":"2008","unstructured":"Andersson, D., Hansen, K.A., Miltersen, P.B., S\u00f8rensen, T.B.: Deterministic Graphical Games Revisited. In: Beckmann, A., Dimitracopoulos, C., L\u00f6we, B. (eds.) CiE 2008. LNCS, vol.\u00a05028, pp. 1\u201310. Springer, Heidelberg (2008)"},{"key":"55_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-642-10631-6_13","volume-title":"Algorithms and Computation","author":"D. Andersson","year":"2009","unstructured":"Andersson, D., Miltersen, P.B.: The Complexity of Solving Stochastic Games on Graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 112\u2013121. Springer, Heidelberg (2009)"},{"key":"55_CR3","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1073\/pnas.53.2.244","volume":"53","author":"R.E. Bellman","year":"1965","unstructured":"Bellman, R.E.: On the application of dynamic programming to the determination of optimal play in chess and checkers. Procedings of the National Academy of Sciences of the United States of America\u00a053, 244\u2013246 (1965)","journal-title":"Procedings of the National Academy of Sciences of the United States of America"},{"key":"55_CR4","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Termination criteria for solving concurrent safety and reachability games. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 197\u2013206 (2009)","DOI":"10.1137\/1.9781611973068.23"},{"key":"55_CR5","doi-asserted-by":"crossref","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 2006, pp. 291\u2013300. IEEE Computer Society (2006)","DOI":"10.1109\/QEST.2006.48"},{"key":"55_CR6","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A. Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation\u00a096, 203\u2013224 (1992)","journal-title":"Information and Computation"},{"key":"55_CR7","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.\u00a013, pp. 51\u201373. American Mathematical Society (1993)","DOI":"10.1090\/dimacs\/013\/04"},{"key":"55_CR8","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":"55_CR9","doi-asserted-by":"crossref","unstructured":"Gillette, D.: Stochastic games with zero stop probabilities. In: Dresher, M., Tucker, A.W., Wolfe, P. (eds.) Contributions to the Theory of Games III. Annals of Mathematics Studies, vol.\u00a039, pp. 179\u2013187. Princeton University Press (1957)","DOI":"10.1515\/9781400882151-011"},{"key":"55_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-540-78499-9_2","volume-title":"Foundations of Software Science and Computational Structures","author":"H. Gimbert","year":"2008","unstructured":"Gimbert, H., Horn, F.: Simple Stochastic Games with Few Random Vertices Are Easy to Solve. In: Amadio, R.M. (ed.) FoSSaCS 2008. LNCS, vol.\u00a04962, pp. 5\u201319. Springer, Heidelberg (2008)"},{"key":"55_CR11","unstructured":"Ibsen-Jensen, R., Miltersen, P.B.: Solving simple stochastic games with few coin toss positions, http:\/\/arxiv.org\/abs\/1112.5255"},{"issue":"1","key":"55_CR12","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0020-0190(02)00455-6","volume":"86","author":"S. Kwek","year":"2003","unstructured":"Kwek, S., Mehlhorn, K.: Optimal search for rationals. Inf. Process. Lett.\u00a086(1), 23\u201326 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"55_CR13","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1137\/1011093","volume":"11","author":"T.M. Liggett","year":"1969","unstructured":"Liggett, T.M., Lippman, S.A.: Stochastic games with perfect information and time average payoff. SIAM Review\u00a011(4), 604\u2013607 (1969)","journal-title":"SIAM Review"},{"key":"55_CR14","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":"55_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J. Moon","year":"1965","unstructured":"Moon, J., Moser, L.: On cliques in graphs. Israel Journal of Mathematics\u00a03, 23\u201328 (1965), doi:10.1007\/BF02760024","journal-title":"Israel Journal of Mathematics"},{"key":"55_CR16","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. Proc. Nat. Acad. Science\u00a039, 1095\u20131100 (1953)","journal-title":"Proc. Nat. Acad. Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T11:34:38Z","timestamp":1744025678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}