{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:54:38Z","timestamp":1758279278703,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642548291"},{"type":"electronic","value":"9783642548307"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54830-7_14","type":"book-chapter","created":{"date-parts":[[2014,3,21]],"date-time":"2014-03-21T13:30:31Z","timestamp":1395408631000},"page":"210-225","source":"Crossref","is-referenced-by-count":6,"title":["Perfect-Information Stochastic Mean-Payoff Parity Games"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Doyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugo","family":"Gimbert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youssouf","family":"Oualhadj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","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":"14_CR2","unstructured":"Billingsley, P. (ed.): Probability and Measure. Wiley-Interscience (1995)"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-642-02658-4_14","volume-title":"Computer Aided Verification","author":"R. Bloem","year":"2009","unstructured":"Bloem, R., Chatterjee, K., Henzinger, T.A., Jobstmann, B.: Better quality in synthesis through quantitative objectives. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol.\u00a05643, pp. 140\u2013156. Springer, Heidelberg (2009)"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-22006-7_13","volume-title":"Automata, Languages and Programming","author":"E. Boros","year":"2011","unstructured":"Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., Manthey, B.: Stochastic mean payoff games: Smoothed\u00a0analysis\u00a0and\u00a0approximation\u00a0schemes. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 147\u2013158. Springer, Heidelberg (2011)"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-85778-5_4","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"P. Bouyer","year":"2008","unstructured":"Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: Cassez, F., Jard, C. (eds.) FORMATS 2008. LNCS, vol.\u00a05215, pp. 33\u201347. Springer, Heidelberg (2008)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-24372-1_11","volume-title":"Automated Technology for Verification and Analysis","author":"P. Bouyer","year":"2011","unstructured":"Bouyer, P., Markey, N., Olschewski, J., Ummels, M.: Measuring permissiveness in parity games: Mean-payoff parity games revisited. In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol.\u00a06996, pp. 135\u2013149. Springer, Heidelberg (2011)"},{"key":"14_CR7","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1090\/S0002-9947-1969-0280205-0","volume":"138","author":"J.R. B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Transactions of the AMS\u00a0138, 295\u2013311 (1969)","journal-title":"Transactions of the AMS"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-22110-1_20","volume-title":"Computer Aided Verification","author":"P. \u010cern\u00fd","year":"2011","unstructured":"\u010cern\u00fd, P., Chatterjee, K., Henzinger, T.A., Radhakrishna, A., Singh, R.: Quantitative synthesis for concurrent programs. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol.\u00a06806, pp. 243\u2013259. Springer, Heidelberg (2011)"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-540-45212-6_9","volume-title":"Embedded Software","author":"A. Chakrabarti","year":"2003","unstructured":"Chakrabarti, A., de Alfaro, L., Henzinger, T.A., Stoelinga, M.: Resource interfaces. In: Alur, R., Lee, I. (eds.) EMSOFT 2003. LNCS, vol.\u00a02855, pp. 117\u2013133. Springer, Heidelberg (2003)"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/978-3-642-14162-1_50","volume-title":"Automata, Languages and Programming","author":"K. Chatterjee","year":"2010","unstructured":"Chatterjee, K., Doyen, L.: Energy parity games. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06199, pp. 599\u2013610. Springer, Heidelberg (2010)"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-22993-0_21","volume-title":"Mathematical Foundations of Computer Science 2011","author":"K. Chatterjee","year":"2011","unstructured":"Chatterjee, K., Doyen, L.: Energy and mean-payoff parity Markov decision processes. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 206\u2013218. Springer, Heidelberg (2011)"},{"issue":"2","key":"14_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.tcs.2012.07.038","volume":"458","author":"K. Chatterjee","year":"2012","unstructured":"Chatterjee, K., Doyen, L.: Energy parity games. TCS\u00a0458(2), 49\u201360 (2012)","journal-title":"TCS"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-03816-7_4","volume-title":"Mathematical Foundations of Computer Science 2009","author":"K. Chatterjee","year":"2009","unstructured":"Chatterjee, K., Henzinger, T.A., Horn, F.: Stochastic games with finitary objectives. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 34\u201354. Springer, Heidelberg (2009)"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A., Jurdzi\u0144ski, M.: Mean-payoff parity games. In: Proc. of LICS, pp. 178\u2013187. IEEE Computer Society (2005)","DOI":"10.1109\/LICS.2005.26"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., Henzinger, T.A.: Quantitative stochastic parity games. In: Proc. of SODA, pp. 121\u2013130. SIAM (2004)","DOI":"10.21236\/ADA603293"},{"issue":"2","key":"14_CR16","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. Comput.\u00a096(2), 203\u2013224 (1992)","journal-title":"Inf. Comput."},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Filar, J.A., Vrieze, K.: Competitive Markov Decision Processes. Springer (1997)","DOI":"10.1007\/978-1-4612-4054-9"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Gimbert, H., Horn, F.: Solving simple stochastic tail games. In: Proc. of SODA, pp. 847\u2013862. SIAM (2010)","DOI":"10.1137\/1.9781611973075.69"},{"key":"14_CR19","unstructured":"Gimbert, H., Oualhadj, Y., Paul, S.: Computing optimal strategies for Markov decision processes with parity and positive-average conditions. Technical report, LaBRI, Universit\u00e9 de Bordeaux II (2011)"},{"issue":"5","key":"14_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"V. Gurvich","year":"1988","unstructured":"Gurvich, V., Karzanov, A., Khachivan, L.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics\u00a028(5), 85\u201391 (1988)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"issue":"3","key":"14_CR21","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzi\u0144ski","year":"1998","unstructured":"Jurdzi\u0144ski, M.: Deciding the winner in parity games is in UP \u2229 co-UP. Information Processing Letters\u00a068(3), 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1137\/1011093","volume":"11","author":"T.A. Liggett","year":"1969","unstructured":"Liggett, T.A., Lippman, S.A.: Stochastic games with perfect information and time average payoff. Siam Review\u00a011, 604\u2013607 (1969)","journal-title":"Siam Review"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Proc. of POPL, pp. 179\u2013190. ACM Press (1989)","DOI":"10.1145\/75277.75293"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"Puterman, M.L.: Markov Decision Processes. John Wiley and Sons (1994)","DOI":"10.1002\/9780470316887"},{"key":"14_CR25","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF01415989","volume":"35","author":"T.E.S. Raghavan","year":"1991","unstructured":"Raghavan, T.E.S., Filar, J.A.: Algorithms for stochastic games \u2014 a survey. ZOR \u2014 Methods and Models of Operations Research\u00a035, 437\u2013472 (1991)","journal-title":"ZOR \u2014 Methods and Models of Operations Research"},{"issue":"1","key":"14_CR26","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1137\/0325013","volume":"25","author":"P.J. Ramadge","year":"1987","unstructured":"Ramadge, P.J., Wonham, W.M.: Supervisory control of a class of discrete-event processes. SIAM Journal of Control and Optimization\u00a025(1), 206\u2013230 (1987)","journal-title":"SIAM Journal of Control and Optimization"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. In: Handbook of Formal Languages, Beyond Words, vol.\u00a03, ch. 7, pp. 389\u2013455. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_7"},{"issue":"1-2","key":"14_CR28","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(98)00009-7","volume":"200","author":"W. Zielonka","year":"1998","unstructured":"Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science\u00a0200(1-2), 135\u2013183 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"1&2","key":"14_CR29","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U. Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. TCS\u00a0158(1&2), 343\u2013359 (1996)","journal-title":"TCS"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54830-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T03:46:52Z","timestamp":1746157612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54830-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642548291","9783642548307"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54830-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}