{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:00Z","timestamp":1759638900538},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319024431"},{"type":"electronic","value":"9783319024448"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-319-02444-8_22","type":"book-chapter","created":{"date-parts":[[2013,8,29]],"date-time":"2013-08-29T05:11:21Z","timestamp":1377753081000},"page":"303-318","source":"Crossref","is-referenced-by-count":1,"title":["Expected Termination Time in BPA Games"],"prefix":"10.1007","author":[{"given":"Dominik","family":"Wojtczak","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"22_CR1","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E. Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM Journal on Computing\u00a038(5), 1987\u20132006 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"22_CR2","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1016\/j.ic.2011.02.002","volume":"209","author":"T. Br\u00e1zdil","year":"2011","unstructured":"Br\u00e1zdil, T., Bro\u017eek, V., Ku\u010dera, A., Obdrz\u00e1lek, J.: Qualitative reachability in stochastic BPA games. Information and Computation\u00a0209(8), 1160\u20131183 (2011)","journal-title":"Information and Computation"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-642-31585-5_16","volume-title":"Automata, Languages, and Programming","author":"T. Br\u00e1zdil","year":"2012","unstructured":"Br\u00e1zdil, T., Ku\u010dera, A., Novotn\u00fd, P., Wojtczak, D.: Minimizing expected termination time in one-counter Markov decision processes. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 141\u2013152. Springer, Heidelberg (2012)"},{"issue":"2","key":"22_CR4","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. Inf. & Comp.\u00a096(2), 203\u2013224 (1992)","journal-title":"Inf. & Comp."},{"key":"22_CR5","unstructured":"de Alfaro, L., Henzinger, T.A.: Concurrent omega-regular games. In: Proc. of the 15th IEEE Symposium on Logic in Computer Science, pp. 141\u2013154. IEEE Computer Society Press (2000)"},{"key":"22_CR6","unstructured":"de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. In: Proc. of FOCS 1998, pp. 564\u2013575 (1998)"},{"issue":"2","key":"22_CR7","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.jcss.2003.07.009","volume":"68","author":"L. Alfaro de","year":"2004","unstructured":"de Alfaro, L., Majumdar, R.: Quantitative solution of omega-regular games. J. Comput. Syst. Sci.\u00a068(2), 374\u2013397 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Esparza, J., Ku\u010dera, A., Mayr, R.: Model checking probabilistic pushdown automata. In: Proc. of 19th IEEE LICS 2004 (2004)","DOI":"10.1109\/LICS.2004.1319596"},{"key":"22_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/978-3-540-70575-8_58","volume-title":"Automata, Languages and Programming","author":"K. Etessami","year":"2008","unstructured":"Etessami, K., Wojtczak, D., Yannakakis, M.: Recursive stochastic games with positive rewards. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 711\u2013723. Springer, Heidelberg (2008)"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-31980-1_17","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"K. Etessami","year":"2005","unstructured":"Etessami, K., Yannakakis, M.: Algorithmic verification of recursive probabilistic state machines. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005. LNCS, vol.\u00a03440, pp. 253\u2013270. Springer, Heidelberg (2005)"},{"key":"22_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-540-31856-9_28","volume-title":"STACS 2005","author":"K. Etessami","year":"2005","unstructured":"Etessami, K., Yannakakis, M.: Recursive Markov chains, stochastic grammars, and monotone systems of non-linear equations. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 340\u2013352. Springer, Heidelberg (2005)"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1007\/11523468_72","volume-title":"Automata, Languages and Programming","author":"K. Etessami","year":"2005","unstructured":"Etessami, K., Yannakakis, M.: Recursive Markov decision processes and recursive stochastic games. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 891\u2013903. Springer, Heidelberg (2005)"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/11672142_52","volume-title":"STACS 2006","author":"K. Etessami","year":"2006","unstructured":"Etessami, K., Yannakakis, M.: Efficient qualitative analysis of classes of recursive Markov decision processes and simple stochastic games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 634\u2013645. Springer, Heidelberg (2006)"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. Logical Methods in Computer Science\u00a04(4) (2008)","DOI":"10.2168\/LMCS-4(4:7)2008"},{"issue":"6","key":"22_CR15","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K. Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing\u00a039(6), 2531\u20132597 (2010)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/978-1-4612-4054-9_2","volume-title":"Competitive Markov Decision Processes","author":"Jerzy Filar","year":"1997","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer (1997)"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proc. of the 8th ACM Symposium on Theory of Computing, STOC\u00a01976, pp. 10\u201322 (1976)","DOI":"10.1145\/800113.803626"},{"key":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-20712-9_7","volume-title":"Computer Science \u2013 Theory 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., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 77\u201390. Springer, Heidelberg (2011)"},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1287\/mnsc.12.5.359","volume":"12","author":"A.J. Hoffman","year":"1966","unstructured":"Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Sci.\u00a012, 359\u2013370 (1966)","journal-title":"Management Sci."},{"key":"22_CR20","unstructured":"Manning, C.D., Sch\u00fctze, H.: Foundations of statistical natural language processing. MIT Press (1999)"},{"issue":"4","key":"22_CR21","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.2307\/2586667","volume":"63","author":"D.A. Martin","year":"1998","unstructured":"Martin, D.A.: The Determinacy of Blackwell Games. J. Symb. Logic\u00a063(4), 1565\u20131581 (1998)","journal-title":"J. Symb. Logic"},{"key":"22_CR22","series-title":"Mathematical Sciences Research Institute Publications","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-1-4612-2822-6_17","volume-title":"Logic from Computer Science","author":"A. Nerode","year":"1992","unstructured":"Nerode, A., Yakhnis, A., Yakhnis, V.: Concurrent programs as strategies in games. In: Logic from Computer Science. Mathematical Sciences Research Institute Publications, vol.\u00a021, pp. 405\u2013479. Springer, New York (1992)"},{"key":"22_CR23","unstructured":"Osborne, M.J., Rubinstein, A.: Course in game theory. MIT Press (1994)"},{"issue":"2","key":"22_CR24","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/mnsc.23.2.117","volume":"23","author":"S.R. Pliska","year":"1976","unstructured":"Pliska, S.R.: Optimization of multitype branching processes. Management Science\u00a023(2), 117\u2013124 (1976)","journal-title":"Management Science"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Proc. of the 16th Symposium on Principles of Programming Languages, pp. 179\u2013190. ACM (1989)","DOI":"10.1145\/75277.75293"},{"issue":"4","key":"22_CR26","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1287\/moor.7.4.582","volume":"7","author":"U.G. Rothblum","year":"1982","unstructured":"Rothblum, U.G., Whittle, P.: Growth optimality for branching Markov decision chains. Mathematics of Operations Research\u00a07(4), 582\u2013601 (1982)","journal-title":"Mathematics of Operations Research"},{"key":"22_CR27","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1953","volume":"39","author":"L.S. Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Nat. Acad. Sci.\u00a039, 1095\u20131100 (1953)","journal-title":"Proc. Nat. Acad. Sci."},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Wojtczak, D.: Expected termination time in BPA games. Technical Report ULCS-13-005, University of Liverpool (2013), http:\/\/www.csc.liv.ac.uk\/research\/techreports","DOI":"10.1007\/978-3-319-02444-8_22"}],"container-title":["Lecture Notes in Computer Science","Automated Technology for Verification and Analysis"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-02444-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T02:27:00Z","timestamp":1646447220000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-02444-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319024431","9783319024448"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-02444-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}