{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:53:08Z","timestamp":1743108788743,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031726200"},{"type":"electronic","value":"9783031726217"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-72621-7_14","type":"book-chapter","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T07:02:34Z","timestamp":1726729354000},"page":"203-220","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Markov Decision Processes with\u00a0Sure Parity and\u00a0Multiple Reachability Objectives"],"prefix":"10.1007","author":[{"given":"Rapha\u00ebl","family":"Berthon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joost-Pieter","family":"Katoen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Winkler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,18]]},"reference":[{"key":"14_CR1","unstructured":"Almagor, S., Kupferman, O., Velner, Y.: Minimizing expected cost under hard Boolean constraints, with applications to quantitative synthesis. In: CONCUR. LIPIcs, vol.\u00a059, pp. 9:1\u20139:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Aminof, B., Kwiatkowska, M., Maubert, B., Murano, A., Rubin, S.: Probabilistic strategy logic. In: IJCAI, pp. 32\u201338. ijcai.org (2019)","DOI":"10.24963\/ijcai.2019\/5"},{"key":"14_CR3","doi-asserted-by":"publisher","unstructured":"Ashok, P., Chatterjee, K., Kret\u00ednsk\u00fd, J., Weininger, M., Winkler, T.: Approximating values of generalized-reachability stochastic games. In: LICS 2020: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science, Saarbr\u00fccken, Germany, 8\u201311 July 2020, pp. 102\u2013115. ACM (2020). https:\/\/doi.org\/10.1145\/3373718.3394761","DOI":"10.1145\/3373718.3394761"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Baier, C., Dubslaff, C., Kl\u00fcppelholz, S.: Trade-off analysis meets probabilistic model checking. In: CSL-LICS, pp. 1:1\u20131:10. ACM (2014)","DOI":"10.1145\/2603088.2603089"},{"key":"14_CR5","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., Katoen, J.-P.: Principles of Model Checking. MIT Press, Cambridge (2008)"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Bellman, R.: A Markovian decision process. J. Math. Mech. 679\u2013684 (1957)","DOI":"10.1512\/iumj.1957.6.56038"},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"Berthon, R., Guha, S., Raskin, J.-F.: Mixing probabilistic and non-probabilistic objectives in Markov decision processes. In: LICS 2020: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science, Saarbr\u00fccken, Germany, 8\u201311 July 2020, pp. 195\u2013208. ACM (2020). https:\/\/doi.org\/10.1145\/3373718.3394805","DOI":"10.1145\/3373718.3394805"},{"key":"14_CR8","doi-asserted-by":"publisher","unstructured":"Berthon, R., Randour, M., Raskin, J.-F.: Threshold constraints with guarantees for parity objectives in Markov decision processes. In: ICALP. LIPIcs, vol.\u00a080, pp. 121:1\u2013121:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.121","DOI":"10.4230\/LIPIcs.ICALP.2017.121"},{"key":"14_CR9","unstructured":"Berthon, R., Katoen, J.-P., Winkler, T.: Markov Decision Processes with Sure Parity and Multiple Reachability Objectives (2024). arXiv:2408.01212"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Bouyer, P., Gonz\u00e1lez, M., Markey, N., Randour, M.: Multi-weighted Markov decision processes with reachability objectives. In: GandALF. EPTCS, vol. 277, pp. 250\u2013264 (2018)","DOI":"10.4204\/EPTCS.277.18"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Brassard, G.: A note on the complexity of cryptography (corresp.). IEEE Trans. Inf. Theory 25(2), 232\u2013233 (1979)","DOI":"10.1109\/TIT.1979.1056010"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-662-46681-0_12","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"T Br\u00e1zdil","year":"2015","unstructured":"Br\u00e1zdil, T., Chatterjee, K., Forejt, V., Ku\u010dera, A.: MultiGain: a controller synthesis tool for MDPs with multiple mean-payoff objectives. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 181\u2013187. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46681-0_12"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2016.10.011","volume":"254","author":"V Bruy\u00e8re","year":"2017","unstructured":"Bruy\u00e8re, V., Filiot, E., Randour, M., Raskin, J.-F.: Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games. Inf. Comput. 254, 259\u2013295 (2017). https:\/\/doi.org\/10.1016\/j.ic.2016.10.011","journal-title":"Inf. Comput."},{"key":"14_CR14","doi-asserted-by":"publisher","unstructured":"Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 252\u2013263. ACM (2017). https:\/\/doi.org\/10.1145\/3055399","DOI":"10.1145\/3055399"},{"key":"14_CR15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-031-13188-2_3","volume-title":"CAV 2022","author":"PF Castro","year":"2022","unstructured":"Castro, P.F., D\u2019Argenio, P.R., Demasi, R., Putruele, L.: Playing against fair adversaries in stochastic games with total rewards. In: Shoham, S., Vizel, Y. (eds.) CAV 2022. LNCS, vol. 13372, pp. 48\u201369. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-13188-2_3"},{"issue":"6","key":"14_CR16","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.ic.2009.07.004","volume":"208","author":"K Chatterjee","year":"2010","unstructured":"Chatterjee, K., Henzinger, T.A., Piterman, N.: Strategy logic. Inf. Comput. 208(6), 677\u2013693 (2010)","journal-title":"Inf. Comput."},{"key":"14_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-023-00411-4","author":"K Chatterjee","year":"2023","unstructured":"Chatterjee, K., Katoen, J.-P., Mohr, S., Weininger, M., Winkler, T.: Stochastic games with lexicographic objectives. Formal Methods Syst. Des. (2023). https:\/\/doi.org\/10.1007\/s10703-023-00411-4","journal-title":"Formal Methods Syst. Des."},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/978-3-030-53291-8_21","volume-title":"Computer Aided Verification","author":"K Chatterjee","year":"2020","unstructured":"Chatterjee, K., Katoen, J.-P., Weininger, M., Winkler, T.: Stochastic games with lexicographic reachability-safety objectives. In: Lahiri, S.K., Wang, C. (eds.) CAV 2020. LNCS, vol. 12225, pp. 398\u2013420. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-53291-8_21"},{"key":"14_CR19","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Kret\u00ednsk\u00e1, Z., Kret\u00ednsk\u00fd, J.: Unifying two views on multiple mean-payoff objectives in Markov decision processes. Log. Methods Comput. Sci. 13(2) (2017). https:\/\/doi.org\/10.23638\/LMCS-13(2:15)2017","DOI":"10.23638\/LMCS-13(2:15)2017"},{"key":"14_CR20","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). https:\/\/doi.org\/10.1007\/11672142_26"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Novotn\u00fd, P., P\u00e9rez, G.A., Raskin, J.-F., Zikelic, D.: Optimizing expectation with guarantees in POMDPs. In: AAAI, pp. 3725\u20133732. AAAI Press (2017)","DOI":"10.1609\/aaai.v31i1.11046"},{"key":"14_CR22","unstructured":"Chatterjee, K., Piterman, N.: Combinations of qualitative winning for stochastic parity games. In: 30th International Conference on Concurrency Theory, CONCUR 2019. LIPIcs, vol. 140, pp. 6:1\u20136:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-121-4"},{"key":"14_CR23","doi-asserted-by":"publisher","unstructured":"Clemente, L., Raskin, J.-F.: Multidimensional beyond worst-case and almost-sure problems for mean-payoff objectives. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, 6\u201310 July 2015, pp. 257\u2013268. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/LICS.2015.33","DOI":"10.1109\/LICS.2015.33"},{"key":"14_CR24","doi-asserted-by":"publisher","unstructured":"Allen Emerson, E., Jutla, C.S., Prasad Sistla, A.: On model checking for the $$\\upmu $$-calculus and its fragments. Theor. Comput. Sci. 258(1\u20132), 491\u2013522 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00034-7","DOI":"10.1016\/S0304-3975(00)00034-7"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Etessami, K., Kwiatkowska, M.Z., Vardi, M.Y., Yannakakis, M.: Multi-objective model checking of Markov decision processes. Logical Methods Comput. Sci. 4(4) (2008)","DOI":"10.2168\/LMCS-4(4:8)2008"},{"key":"14_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-642-33386-6_25","volume-title":"Automated Technology for Verification and Analysis","author":"V Forejt","year":"2012","unstructured":"Forejt, V., Kwiatkowska, M., Parker, D.: Pareto curves for probabilistic model checking. In: Chakraborty, S., Mukund, M. (eds.) ATVA 2012. LNCS, pp. 317\u2013332. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33386-6_25"},{"key":"14_CR27","volume-title":"Convex Polytopes","author":"B Gr\u00fcnbaum","year":"1967","unstructured":"Gr\u00fcnbaum, B., Klee, V., Perles, M.A., Shephard, G.C.: Convex Polytopes, vol. 16. Springer, Cham (1967)"},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-030-45190-5_17","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"EM Hahn","year":"2020","unstructured":"Hahn, E.M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., Wojtczak, D.: Good-for-MDPs automata for probabilistic analysis and reinforcement learning. In: TACAS 2020. LNCS, vol. 12078, pp. 306\u2013323. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45190-5_17"},{"issue":"7","key":"14_CR29","doi-asserted-by":"publisher","first-page":"1483","DOI":"10.1007\/s10817-020-09574-9","volume":"64","author":"A Hartmanns","year":"2020","unstructured":"Hartmanns, A., Junges, S., Katoen, J.-P., Quatmann, T.: Multi-cost bounded tradeoff analysis in MDP. J. Autom. Reason. 64(7), 1483\u20131522 (2020)","journal-title":"J. Autom. Reason."},{"issue":"4","key":"14_CR30","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s10009-021-00633-z","volume":"24","author":"C Hensel","year":"2022","unstructured":"Hensel, C., Junges, S., Katoen, J.-P., Quatmann, T., Volk, M.: The probabilistic model checker Storm. Int. J. Softw. Tools Technol. Transf. 24(4), 589\u2013610 (2022)","journal-title":"Int. J. Softw. Tools Technol. Transf."},{"issue":"3","key":"14_CR31","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M Jurdzinski","year":"1998","unstructured":"Jurdzinski, M.: Deciding the winner in parity games is in UP $$\\cap $$ co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(98)00150-1","journal-title":"Inf. Process. Lett."},{"key":"14_CR32","unstructured":"Kiefer, S., Mayr, R., Shirmohammadi, M., Totzke, P.: Strategy complexity of parity objectives in countable MDPs. In: CONCUR. LIPIcs, vol. 171, pp. 39:1\u201339:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"14_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-642-22110-1_47","volume-title":"Computer Aided Verification","author":"M Kwiatkowska","year":"2011","unstructured":"Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 585\u2013591. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22110-1_47"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"Miura, S., Wray, K.H., Zilberstein, S.: Heuristic search for SSPs with lexicographic preferences over multiple costs. In: SOCS, pp. 127\u2013135. AAAI Press (2022)","DOI":"10.1609\/socs.v15i1.21760"},{"key":"14_CR35","series-title":"Wiley Series in Probability and Statistics","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"ML Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics, Wiley, Hoboken (1994)"},{"issue":"2","key":"14_CR36","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10703-016-0262-7","volume":"50","author":"M Randour","year":"2017","unstructured":"Randour, M., Raskin, J.-F., Sankur, O.: Percentile queries in multi-dimensional Markov decision processes. Formal Methods Syst. Des. 50(2), 207\u2013248 (2017). https:\/\/doi.org\/10.1007\/s10703-016-0262-7","journal-title":"Formal Methods Syst. Des."},{"key":"14_CR37","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1613\/jair.3987","volume":"48","author":"DM Roijers","year":"2013","unstructured":"Roijers, D.M., Vamplew, P., Whiteson, S., Dazeley, R.: A survey of multi-objective sequential decision-making. J. Artif. Intell. Res. 48, 67\u2013113 (2013). https:\/\/doi.org\/10.1613\/jair.3987","journal-title":"J. Artif. Intell. Res."},{"key":"14_CR38","doi-asserted-by":"publisher","unstructured":"Schewe, S., Weinert, A., Zimmermann, M.: Parity games with weights. Log. Methods Comput. Sci. 15(3) (2019). https:\/\/doi.org\/10.23638\/LMCS-15(3:20)2019","DOI":"10.23638\/LMCS-15(3:20)2019"},{"key":"14_CR39","doi-asserted-by":"publisher","unstructured":"Winkler, T., Weininger, M.: Stochastic games with disjunctions of multiple objectives. In: GandALF. EPTCS, vol. 346, pp. 83\u2013100 (2021). https:\/\/doi.org\/10.4204\/EPTCS.346.6","DOI":"10.4204\/EPTCS.346.6"},{"key":"14_CR40","doi-asserted-by":"crossref","unstructured":"Wray, K.H., Zilberstein, S., Mouaddib, A.-I.: Multi-objective MDPs with conditional lexicographic reward preferences. In: AAAI, pp. 3418\u20133424. AAAI Press (2015)","DOI":"10.1609\/aaai.v29i1.9647"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72621-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T07:07:22Z","timestamp":1726729642000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72621-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031726200","9783031726217"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72621-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"18 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easychair.org\/smart-program\/RP24\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}