{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T21:06:54Z","timestamp":1789938414582,"version":"4.0.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2017,1,5]],"date-time":"2017-01-05T00:00:00Z","timestamp":1483574400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["279499"],"award-info":[{"award-number":["279499"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","award":["87562"],"award-info":[{"award-number":["87562"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Form Methods Syst Des"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s10703-016-0262-7","type":"journal-article","created":{"date-parts":[[2017,1,5]],"date-time":"2017-01-05T12:53:23Z","timestamp":1483620803000},"page":"207-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Percentile queries in multi-dimensional Markov decision processes"],"prefix":"10.1007","volume":"50","author":[{"given":"Mickael","family":"Randour","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Fran\u00e7ois","family":"Raskin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ocan","family":"Sankur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,1,5]]},"reference":[{"key":"262_CR1","doi-asserted-by":"publisher","unstructured":"Baier C, Daum M, Dubslaff C, Klein J, Kl\u00fcppelholz S (2014) Energy-utility quantiles. In: NASA formal methods, LNCS 8430, Springer, pp 285\u2013299","DOI":"10.1007\/978-3-319-06200-6_24"},{"key":"262_CR2","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1287\/moor.16.3.580","volume":"16","author":"DP Bertsekas","year":"1991","unstructured":"Bertsekas DP, Tsitsiklis JN (1991) An analysis of stochastic shortest path problems. Math Oper Res 16:580\u2013595","journal-title":"Math Oper Res"},{"key":"262_CR3","doi-asserted-by":"publisher","unstructured":"Boker U, Henzinger TA (2014) Exact and approximate determinization of discounted-sum automata. Log Methods Comput Sci 10(1)","DOI":"10.2168\/LMCS-10(1:10)2014"},{"key":"262_CR4","doi-asserted-by":"publisher","unstructured":"Boker U, Henzinger TA, Otop J (2015) The target discounted-sum problem. In: IEEE Proceedings of LICS, pp 750\u2013761","DOI":"10.1109\/LICS.2015.74"},{"key":"262_CR5","unstructured":"Br\u00e1zdil T, Chen T, Forejt V, Novotn\u00fd P, Simaitis A (2013) Solvency Markov decision processes with interest. In: Proceedings of FSTTCS, volume\u00a024 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 487\u2013499"},{"issue":"13","key":"262_CR6","first-page":"1","volume":"10","author":"T Br\u00e1zdil","year":"2014","unstructured":"Br\u00e1zdil T, Brozek V, Chatterjee K, Forejt V, Kucera A (2014) Markov decision processes with multiple long-run average objectives. Log Methods Comput Sci 10(13):1\u201329","journal-title":"Log Methods Comput Sci"},{"key":"262_CR7","unstructured":"Bruy\u00e8re V, Filiot E, Randour M, Raskin J-F (2014) Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games. In: Proceedings of STACS, volume\u00a025 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 199\u2013213"},{"issue":"1 3","key":"262_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.tcs.2007.07.047","volume":"388","author":"K Chatterjee","year":"2007","unstructured":"Chatterjee K (2007) Concurrent games with tail objectives. Theore Comput Sci 388(1 3):181\u2013198","journal-title":"Theore Comput Sci"},{"key":"262_CR9","unstructured":"Chatterjee K, Doyen L, Henzinger TA, Raskin J-F (2010) Generalized mean-payoff and energy games. In: Proceedings of FSTTCS, volume\u00a08 of LIPIcs, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp 505\u2013516"},{"key":"262_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.ic.2015.03.010","volume":"242","author":"K Chatterjee","year":"2015","unstructured":"Chatterjee K, Doyen L, Randour M, Raskin J-F (2015) Looking at mean-payoff and total-payoff through windows. Inf Comput 242:25\u201352","journal-title":"Inf Comput"},{"key":"262_CR11","doi-asserted-by":"publisher","unstructured":"Chatterjee K, Forejt V, Wojtczak D (2013) Multi-objective discounted reward verification in graphs and MDPs. In: Proceedings of LPAR, LNCS 8312, Springer, pp 228\u2013242","DOI":"10.1007\/978-3-642-45221-5_17"},{"key":"262_CR12","doi-asserted-by":"publisher","unstructured":"Chatterjee K, Henzinger TA (2009) Probabilistic systems with limsup and liminf objectives. In: Brattka MAV, L\u00f6we VGB (eds), Infinity in logic and computation, LNCS 5489, Springer, pp 32\u201345","DOI":"10.1007\/978-3-642-03092-5_4"},{"key":"262_CR13","doi-asserted-by":"publisher","unstructured":"Chatterjee K, Kom\u00e1rkov\u00e1 Z, Kret\u00ednsk\u00fd J (2015) Unifying two views on multiple mean-payoff objectives in Markov decision processes. In: Proceedings of LICS, pp 244\u2013256","DOI":"10.1109\/LICS.2015.32"},{"key":"262_CR14","doi-asserted-by":"publisher","unstructured":"Chatterjee K, Majumdar R, Henzinger TA (2006) Markov decision processes with multiple objectives. In: Proceedings of STACS, LNCS 3884, Springer, pp 325\u2013336","DOI":"10.1007\/11672142_26"},{"issue":"3\u20134","key":"262_CR15","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 (2014) Strategy synthesis for multi-dimensional quantitative objectives. Acta Inform 51(3\u20134):129\u2013163","journal-title":"Acta Inform"},{"key":"262_CR16","unstructured":"de\u00a0Alfaro L (1997) Formal verification of probabilistic systems. Ph.D. thesis, Stanford University"},{"key":"262_CR17","doi-asserted-by":"publisher","unstructured":"de\u00a0Alfaro L (1999) Computing minimum and maximum reachability times in probabilistic systems. In: Proceedings of CONCUR, LNCS 1664, Springer, pp 66\u201381","DOI":"10.1007\/3-540-48320-9_7"},{"key":"262_CR18","doi-asserted-by":"publisher","unstructured":"Etessami K, Kwiatkowska M, Vardi MY, Yannakakis M (2008) Multi-objective model checking of Markov decision processes. Log Methods in Comput Sci 4(4)","DOI":"10.2168\/LMCS-4(4:8)2008"},{"issue":"1","key":"262_CR19","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/9.362904","volume":"40","author":"JA Filar","year":"1995","unstructured":"Filar JA, Krass D, Ross KW (1995) Percentile performance criteria for limiting average Markov decision processes. IEEE Trans Autom Control 40(1):2\u201310","journal-title":"IEEE Trans Autom Control"},{"key":"262_CR20","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"key":"262_CR21","doi-asserted-by":"publisher","unstructured":"Goldreich O (2006) On promise problems: a survey. In: Goldreich O, Rosenberg A, Selman AL (eds), Theoretical computer science, essays in memory of Shimon Even, LNCS 3895, Springer, pp 254\u2013290","DOI":"10.1007\/11685654_12"},{"key":"262_CR22","doi-asserted-by":"publisher","unstructured":"Haase C, Kiefer S (2015) The odds of staying on budget. In: Proceedings of ICALP, LNCS 9135, Springer, pp 234\u2013246","DOI":"10.1007\/978-3-662-47666-6_19"},{"issue":"2","key":"262_CR23","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.ipl.2015.09.015","volume":"116","author":"C Haase","year":"2016","unstructured":"Haase C, Kiefer S (2016) The complexity of the Kth largest subset problem and related problems. Inf Process Lett 116(2):111\u2013115","journal-title":"Inf Process Lett"},{"issue":"4","key":"262_CR24","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1145\/322092.322097","volume":"25","author":"DB Johnson","year":"1978","unstructured":"Johnson DB, Kashdan SD (1978) Lower bounds for selection in X + Y and other multisets. J ACM 25(4):556\u2013570","journal-title":"J ACM"},{"issue":"3","key":"262_CR25","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky ML (1961) Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Ann Math 74(3):437\u2013455","journal-title":"Ann Math"},{"issue":"2","key":"262_CR26","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1016\/S0096-3003(03)00158-9","volume":"149","author":"Y Ohtsubo","year":"2004","unstructured":"Ohtsubo Y (2004) Optimal threshold probability in undiscounted Markov decision processes with a target set. Appl Math Comput 149(2):519\u2013532","journal-title":"Appl Math Comput"},{"key":"262_CR27","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes: discrete stochastic dynamic programming","author":"ML Puterman","year":"1994","unstructured":"Puterman ML (1994) Markov decision processes: discrete stochastic dynamic programming, 1st edn. Wiley, New York","edition":"1"},{"key":"262_CR28","doi-asserted-by":"publisher","unstructured":"Randour M, Raskin J-F, Sankur O (2015) Percentile queries in multi-dimensional Markov decision processes. In: Proceedings of CAV, LNCS 9206, Springer, pp 123\u2013139","DOI":"10.1007\/978-3-319-21690-4_8"},{"key":"262_CR29","doi-asserted-by":"publisher","unstructured":"Randour M, Raskin J-F, Sankur O (2015) Variations on the stochastic shortest path problem. In: Proceedings of VMCAI, LNCS 8931, Springer, pp 1\u201318","DOI":"10.1007\/978-3-662-46081-8_1"},{"issue":"4","key":"262_CR30","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 (2013) Markov decision processes associated with two threshold probability criteria. J Contro Theory Appl 11(4):548\u2013557","journal-title":"J Contro Theory Appl"},{"issue":"5","key":"262_CR31","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda S (1991) PP is as hard as the polynomial-time hierarchy. SIAM J Comput 20(5):865\u2013877","journal-title":"SIAM J Comput"},{"issue":"2","key":"262_CR32","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.orl.2008.12.003","volume":"37","author":"M Tracol","year":"2009","unstructured":"Tracol M (2009) Fast convergence to state-action frequency polytopes for MDPs. Oper Res Lett 37(2):123\u2013126","journal-title":"Oper Res Lett"},{"issue":"1\u20133","key":"262_CR33","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2006.08.017","volume":"369","author":"SD Travers","year":"2006","unstructured":"Travers SD (2006) The complexity of membership problems for circuits over sets of integers. Theor Comput Sci 369(1\u20133):211\u2013229","journal-title":"Theor Comput Sci"},{"key":"262_CR34","doi-asserted-by":"publisher","unstructured":"Ummels M, Baier C (2013) Computing quantiles in Markov reward models. In: Proceedings of FOSSACS, LNCS 7794, Springer, pp 353\u2013368","DOI":"10.1007\/978-3-642-37075-5_23"},{"key":"262_CR35","doi-asserted-by":"publisher","unstructured":"Vardi MY (1985) Automatic verification of probabilistic concurrent finite-state programs. In: IEEE Proceedings of FOCS, pp 327\u2013338","DOI":"10.1109\/SFCS.1985.12"},{"issue":"2","key":"262_CR36","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1006\/jmaa.1993.1093","volume":"173","author":"DJ White","year":"1993","unstructured":"White DJ (1993) Minimizing a threshold probability in discounted Markov decision processes. J Math Anal Appl 173(2):634\u2013646","journal-title":"J Math Anal Appl"},{"issue":"1","key":"262_CR37","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jmaa.1998.6203","volume":"231","author":"W Congbin","year":"1999","unstructured":"Congbin W, Lin Y (1999) Minimizing risk models in Markov decision processes with policies depending on target values. J Math Anal Appl 231(1):47\u201367","journal-title":"J Math Anal Appl"},{"key":"262_CR38","unstructured":"Xu H, Mannor S (2011) Probabilistic goal Markov decision processes. In: Proceedings of IJCAI, pp 2046\u20132052"}],"container-title":["Formal Methods in System Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10703-016-0262-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10703-016-0262-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10703-016-0262-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T14:56:53Z","timestamp":1601305013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10703-016-0262-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,5]]},"references-count":38,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["262"],"URL":"https:\/\/doi.org\/10.1007\/s10703-016-0262-7","relation":{},"ISSN":["0925-9856","1572-8102"],"issn-type":[{"value":"0925-9856","type":"print"},{"value":"1572-8102","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,5]]}}}