{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:24:06Z","timestamp":1762298646322},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319631202"},{"type":"electronic","value":"9783319631219"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-63121-9_18","type":"book-chapter","created":{"date-parts":[[2017,7,24]],"date-time":"2017-07-24T08:05:15Z","timestamp":1500883515000},"page":"367-381","source":"Crossref","is-referenced-by-count":5,"title":["The Cost of Exactness in Quantitative Reachability"],"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":"Thomas A.","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,25]]},"reference":[{"key":"18_CR1","unstructured":"Andersson, D.: An improved algorithm for discounted payoff games. In: Proceedings of 11th ESSLLI Student Session, pp. 91\u201398 (2006)"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Blondin, M., Finkel, A., G\u00f6ller, S., Haase, C., McKenzie, P.: Reachability in two-dimensional vector addition systems with states is PSPACE-complete. In: Proceedings of LICS: Symposium on Logic in Computer Science, pp. 32\u201343. IEEE Computer Society (2015)","DOI":"10.1109\/LICS.2015.14"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Boker, U., Henzinger, T.A., Otop, J.: The target discounted-sum problem. In: Proceeings of LICS: Symposium on Logic in Computer Science, pp. 750\u2013761. IEEE Computer Society (2015)","DOI":"10.1109\/LICS.2015.74"},{"key":"18_CR4","unstructured":"Bonet, B., Geffner, H.: Solving POMDPs: RTDP-Bel vs. point-based algorithms. In: Proceedings of IJCAI: International Joint Conference on Artificial Intelligence, pp. 1641\u20131646 (2009)"},{"key":"18_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. 5215, pp. 33\u201347. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-85778-5_4"},{"key":"18_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/978-3-642-14162-1_40","volume-title":"Automata, Languages and Programming","author":"T Br\u00e1zdil","year":"2010","unstructured":"Br\u00e1zdil, T., Jan\u010dar, P., Ku\u010dera, A.: Reachability games on extended vector addition systems with states. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 478\u2013489. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14162-1_40"},{"key":"18_CR7","unstructured":"Brihaye, T., Geeraerts, G., Haddad, A., Monmege, B.: To reach or not to reach? efficient algorithms for total-payoff games. In: Proceedings of CONCUR: Concurrency Theory. LIPIcs, vol. 42, pp. 297\u2013310. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)"},{"issue":"2","key":"18_CR8","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10703-010-0105-x","volume":"38","author":"L Brim","year":"2011","unstructured":"Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.-F.: Faster algorithms for mean-payoff games. Formal Methods Syst. Des. 38(2), 97\u2013118 (2011)","journal-title":"Formal Methods Syst. Des."},{"key":"18_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. 2855, pp. 117\u2013133. Springer, Heidelberg (2003). doi: 10.1007\/978-3-540-45212-6_9"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Chmelik, M.: Indefinite-horizon reachability in Goal-DEC-POMDPs. In: Proceedings of ICAPS: International Conference on Automated Planning and Scheduling, pp. 88\u201396. AAAI Press (2016)","DOI":"10.1609\/icaps.v26i1.13737"},{"key":"18_CR11","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.artint.2016.01.007","volume":"234","author":"K Chatterjee","year":"2016","unstructured":"Chatterjee, K., Chmelik, M., Gupta, R., Kanodia, A.: Optimal cost almost-sure reachability in POMDPs. Artif. Intell. 234, 26\u201348 (2016)","journal-title":"Artif. Intell."},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-45221-5_17","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"K Chatterjee","year":"2013","unstructured":"Chatterjee, K., Forejt, V., Wojtczak, D.: Multi-objective discounted reward verification in graphs and MDPs. In: McMillan, K., Middeldorp, A., Voronkov, A. (eds.) LPAR 2013. LNCS, vol. 8312, pp. 228\u2013242. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-45221-5_17"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/11672142_26","volume-title":"STACS 2006","author":"K Chatterjee","year":"2006","unstructured":"Chatterjee, K., Majumdar, R., Henzinger, T.A.: Markov decision processes with multiple objectives. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 325\u2013336. Springer, Heidelberg (2006). doi: 10.1007\/11672142_26"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-642-40184-8_35","volume-title":"CONCUR 2013 \u2013 Concurrency Theory","author":"K Chatterjee","year":"2013","unstructured":"Chatterjee, K., Velner, Y.: Hyperplane Separation technique for multidimensional mean-payoff games. In: D\u2019Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013. LNCS, vol. 8052, pp. 500\u2013515. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40184-8_35"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-642-32940-1_25","volume-title":"CONCUR 2012 \u2013 Concurrency Theory","author":"T Chen","year":"2012","unstructured":"Chen, T., Forejt, V., Kwiatkowska, M., Simaitis, A., Trivedi, A., Ummels, M.: Playing stochastic games precisely. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012. LNCS, vol. 7454, pp. 348\u2013363. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-32940-1_25"},{"issue":"2","key":"18_CR16","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8(2), 109\u2013113 (1979)","journal-title":"Int. J. Game Theory"},{"key":"18_CR17","volume-title":"Competitive Markov Decision Processes","author":"J Filar","year":"1997","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer-Verlag, Heidelberg (1997)"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Filiot, E., Gentilini, R., Raskin, J.-F.: Quantitative languages defined by functional automata. Logical Methods Comput. Sci. 11(3) (2015)","DOI":"10.2168\/LMCS-11(3:14)2015"},{"issue":"5","key":"18_CR19","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"VA Gurvich","year":"1988","unstructured":"Gurvich, V.A., Karzanov, A.V., Khachiyan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phy. 28(5), 85\u201391 (1988)","journal-title":"USSR Comput. Math. Math. Phy."},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-04081-8_25","volume-title":"CONCUR 2009 - Concurrency Theory","author":"C Haase","year":"2009","unstructured":"Haase, C., Kreutzer, S., Ouaknine, J., Worrell, J.: Reachability in succinct and parametric one-counter automata. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 369\u2013383. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-04081-8_25"},{"issue":"1","key":"18_CR21","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2432622.2432623","volume":"60","author":"TD Hansen","year":"2013","unstructured":"Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. J. ACM 60(1), 1:1\u20131:16 (2013)","journal-title":"J. ACM"},{"key":"18_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-319-24537-9_5","volume-title":"Reachability Problems","author":"P Hunter","year":"2015","unstructured":"Hunter, P.: Reachability in succinct one-counter games. In: Boja\u0144czyk, M., Lasota, S., Potapov, I. (eds.) RP 2015. LNCS, vol. 9328, pp. 37\u201349. Springer, Cham (2015). doi: 10.1007\/978-3-319-24537-9_5"},{"key":"18_CR23","unstructured":"Hunter, P., Raskin, J.-F.: Quantitative games with interval objectives. In: Proceedings of FSTTCS, vol. 29 of LIPIcs, pp. 365\u2013377. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)"},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-662-47666-6_21","volume-title":"Automata, Languages, and Programming","author":"M Jurdzi\u0144ski","year":"2015","unstructured":"Jurdzi\u0144ski, M., Lazi\u0107, R., Schmitz, S.: Fixed-dimensional energy games are in pseudo-polynomial time. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 260\u2013272. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-47666-6_21"},{"key":"18_CR25","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"RM Karp","year":"1978","unstructured":"Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23, 309\u2013311 (1978)","journal-title":"Discrete Math."},{"issue":"1","key":"18_CR26","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1006\/jagm.2001.1201","volume":"42","author":"M Nyk\u00e4nen","year":"2002","unstructured":"Nyk\u00e4nen, M., Ukkonen, E.: The exact path length problem. J. Algorithms 42(1), 41\u201353 (2002)","journal-title":"J. Algorithms"},{"key":"18_CR27","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes","author":"ML Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes. Wiley, Hoboken (1994)"},{"key":"18_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-41036-9_18","volume-title":"Reachability Problems","author":"J Reichert","year":"2013","unstructured":"Reichert, J.: On the complexity of counter reachability games. In: Abdulla, P.A., Potapov, I. (eds.) RP 2013. LNCS, vol. 8169, pp. 196\u2013208. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-41036-9_18"},{"key":"18_CR29","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.ic.2015.03.001","volume":"241","author":"Y Velner","year":"2015","unstructured":"Velner, Y., Chatterjee, K., Doyen, L., Henzinger, T.A., Rabinovich, A.M., Raskin, J.-F.: The complexity of multi-mean-payoff and multi-energy games. Inf. Comput. 241, 177\u2013196 (2015)","journal-title":"Inf. Comput."},{"issue":"1&2","key":"18_CR30","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 158(1&2), 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Models, Algorithms, Logics and Tools"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-63121-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T17:29:15Z","timestamp":1692898155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-63121-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319631202","9783319631219"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-63121-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}