{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:17:18Z","timestamp":1770977838379,"version":"3.50.1"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319216898","type":"print"},{"value":"9783319216904","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21690-4_8","type":"book-chapter","created":{"date-parts":[[2015,7,15]],"date-time":"2015-07-15T06:08:27Z","timestamp":1436940507000},"page":"123-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Percentile Queries in Multi-dimensional Markov Decision Processes"],"prefix":"10.1007","author":[{"given":"Mickael","family":"Randour","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Fran\u00e7ois","family":"Raskin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ocan","family":"Sankur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,16]]},"reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-319-06200-6_24","volume-title":"NASA Formal Methods","author":"C Baier","year":"2014","unstructured":"Baier, C., Daum, M., Dubslaff, C., Klein, J., Kl\u00fcppelholz, S.: Energy-utility quantiles. In: Badger, J.M., Rozier, K.Y. (eds.) NFM 2014. LNCS, vol. 8430, pp. 285\u2013299. Springer, Heidelberg (2014)"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1287\/moor.16.3.580","volume":"16","author":"DP Bertsekas","year":"1991","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: An analysis of stochastic shortest path problems. Math. Oper. Res. 16, 580\u2013595 (1991)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"8_CR3","first-page":"1","volume":"10","author":"U Boker","year":"2014","unstructured":"Boker, U., Henzinger, T.A.: Exact and approximate determinization of discounted-sum automata. LMCS 10(1), 1\u201333 (2014)","journal-title":"LMCS"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Boker, U., Henzinger, T.A., Otop, J.: The target discounted-sum problem. In: Proceedings of LICS. IEEE Computer Society (2015)","DOI":"10.1109\/LICS.2015.74"},{"key":"8_CR5","unstructured":"Br\u00e1zdil, T., Chen, T., Forejt, V., Novotn\u00fd, P., Simaitis, A.: Solvency Markov decision processes with interest. In: Proceedings of FSTTCS, LIPIcs, vol. 24, pp. 487\u2013499. Schloss Dagstuhl - LZI (2013)"},{"issue":"13","key":"8_CR6","first-page":"1","volume":"10","author":"T Br\u00e1zdil","year":"2014","unstructured":"Br\u00e1zdil, T., Brozek, V., Chatterjee, K., Forejt, V., Kucera, A.: Markov decision processes with multiple long-run average objectives. LMCS 10(13), 1\u201329 (2014)","journal-title":"LMCS"},{"key":"8_CR7","unstructured":"Bruy\u00e8re, V., Filiot, E., Randour, M., Raskin, J.-F.: Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games. In: Proceedings of STACS, LIPIcs, vol. 25, pp. 199\u2013213. Schloss Dagstuhl - LZI (2014)"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-319-02444-8_10","volume-title":"Automated Technology for Verification and Analysis","author":"K Chatterjee","year":"2013","unstructured":"Chatterjee, K., Doyen, L., Randour, M., Raskin, J.-F.: Looking at mean-payoff and total-payoff through windows. In: Van Hung, D., Ogawa, M. (eds.) ATVA 2013. LNCS, vol. 8172, pp. 118\u2013132. Springer, Heidelberg (2013)"},{"key":"8_CR9","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-19 2013. LNCS, vol. 8312, pp. 228\u2013242. Springer, Heidelberg (2013)"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-642-03092-5_4","volume-title":"Infinity in Logic and Computation","author":"K Chatterjee","year":"2009","unstructured":"Chatterjee, K., Henzinger, T.A.: Probabilistic systems with limsup and liminf objectives. In: Archibald, M., Brattka, V., Goranko, V., L\u00f6we, B. (eds.) ILC 2007. LNCS, vol. 5489, pp. 32\u201345. Springer, Heidelberg (2009)"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Kom\u00e1rkov\u00e1, Z., Kret\u00ednsk\u00fd, J.: Unifying two views on multiple mean-payoff objectives in Markov decision processes. In: Proceedings of LICS. IEEE Computer Society (2015)","DOI":"10.1109\/LICS.2015.32"},{"key":"8_CR12","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)"},{"issue":"3\u20134","key":"8_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s00236-013-0182-6","volume":"51","author":"K Chatterjee","year":"2014","unstructured":"Chatterjee, K., Randour, M., Raskin, J.-F.: Strategy synthesis for multi-dimensional quantitative objectives. Acta Inform. 51(3\u20134), 129\u2013163 (2014)","journal-title":"Acta Inform."},{"key":"8_CR14","unstructured":"de Alfaro, L.: Formal verification of probabilistic systems. Ph.D. thesis, Stanford University (1997)"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/3-540-48320-9_7","volume-title":"CONCUR\u201999. Concurrency Theory","author":"L Alfaro de","year":"1999","unstructured":"de Alfaro, L.: Computing minimum and maximum reachability times in probabilistic systems. In: Baeten, J.C.M., Mauw, S. (eds.) CONCUR 1999. LNCS, vol. 1664, pp. 66\u201381. Springer, Heidelberg (1999)"},{"issue":"4","key":"8_CR16","first-page":"1","volume":"4","author":"K Etessami","year":"2008","unstructured":"Etessami, K., Kwiatkowska, M.Z., Vardi, M.Y., Yannakakis, M.: Multi-objective model checking of Markov decision processes. LMCS 4(4), 1\u201321 (2008)","journal-title":"LMCS"},{"issue":"1","key":"8_CR17","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/9.362904","volume":"40","author":"JA Filar","year":"1995","unstructured":"Filar, J.A., Krass, D., Ross, K.W.: Percentile performance criteria for limiting average Markov decision processes. IEEE Trans. Aut. Control 40(1), 2\u201310 (1995)","journal-title":"IEEE Trans. Aut. Control"},{"key":"8_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Michael R Garey","year":"1979","unstructured":"Garey, Michael R., Johnson, David S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11685654_12","volume-title":"Theoretical Computer Science","author":"O Goldreich","year":"2006","unstructured":"Goldreich, O.: On promise problems: a survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254\u2013290. Springer, Heidelberg (2006)"},{"key":"8_CR20","unstructured":"Haase, C., Kiefer, S.: The complexity of the Kth largest subset problem and related problems. CoRR, abs\/1501.06729 (2015)"},{"key":"8_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-662-47666-6_19","volume-title":"Automata, Languages, and Programming","author":"C Haase","year":"2015","unstructured":"Haase, C., Kiefer, S.: The odds of staying on budget. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 234\u2013246. Springer, Heidelberg (2015)"},{"issue":"2","key":"8_CR22","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1016\/S0096-3003(03)00158-9","volume":"149","author":"Y Ohtsubo","year":"2004","unstructured":"Ohtsubo, Y.: Optimal threshold probability in undiscounted Markov decision processes with a target set. Appl. Math. Comput. 149(2), 519\u2013532 (2004)","journal-title":"Appl. Math. Comput."},{"key":"8_CR23","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, 1st edn. Wiley, New York (1994)","edition":"1"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Randour, M., Raskin, J.-F., Sankur, O.: Percentile queries in multi-dimensional Markov decision processes. CoRR, abs\/1410.4801 (2014)","DOI":"10.1007\/978-3-319-21690-4_8"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"M Randour","year":"2015","unstructured":"Randour, M., Raskin, J.-F., Sankur, O.: Variations on the stochastic shortest path problem. In: D\u2019Souza, D., Lal, A., Larsen, K.G. (eds.) VMCAI 2015. LNCS, vol. 8931, pp. 1\u201318. Springer, Heidelberg (2015)"},{"issue":"4","key":"8_CR26","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/s11768-013-2194-8","volume":"11","author":"M Sakaguchi","year":"2013","unstructured":"Sakaguchi, M., Ohtsubo, Y.: Markov decision processes associated with two threshold probability criteria. J. Control Theor. Appl. 11(4), 548\u2013557 (2013)","journal-title":"J. Control Theor. Appl."},{"issue":"5","key":"8_CR27","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"8_CR28","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2006.08.017","volume":"369","author":"SD Travers","year":"2006","unstructured":"Travers, S.D.: The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci. 369(1\u20133), 211\u2013229 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-37075-5_23","volume-title":"Foundations of Software Science and Computation Structures","author":"M Ummels","year":"2013","unstructured":"Ummels, M., Baier, C.: Computing quantiles in Markov reward models. In: Pfenning, F. (ed.) FOSSACS 2013 (ETAPS 2013). LNCS, vol. 7794, pp. 353\u2013368. Springer, Heidelberg (2013)"},{"issue":"2","key":"8_CR30","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1006\/jmaa.1993.1093","volume":"173","author":"DJ White","year":"1993","unstructured":"White, D.J.: Minimizing a threshold probability in discounted Markov decision processes. J. Math. Anal. Appl. 173(2), 634\u2013646 (1993)","journal-title":"J. Math. Anal. Appl."},{"issue":"1","key":"8_CR31","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jmaa.1998.6203","volume":"231","author":"C Wu","year":"1999","unstructured":"Wu, C., Lin, Y.: Minimizing risk models in Markov decision processes with policies depending on target values. J. Math. Anal. Appl. 231(1), 47\u201367 (1999)","journal-title":"J. Math. Anal. Appl."},{"key":"8_CR32","unstructured":"Xu, H., Mannor, S.: Probabilistic goal Markov decision processes. In: IJCAI, pp. 2046\u20132052 (2011)"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21690-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T03:09:11Z","timestamp":1652843351000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-21690-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319216898","9783319216904"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21690-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}