{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:29:14Z","timestamp":1758266954318,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_19","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"234-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["The Odds of Staying on Budget"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Haase","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Kiefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"5","key":"19_CR1","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Bro, P.: Miltersen. On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987\u20132006 (2009)","journal-title":"SIAM J. Comput."},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Baier, C., Dubslaff, C., Kl\u00fcppelholz, S.: Trade-off analysis meets probabilistic model checking. In: Proc. CSL-LICS, pp. 1:1\u20131:10. ACM (2014)","DOI":"10.1145\/2603088.2603089"},{"key":"19_CR3","unstructured":"Baier, C., Katoen, J.-P.: Principles of Model Checking. MIT Press (2008)"},{"key":"19_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-642-54862-8_43","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"C Baier","year":"2014","unstructured":"Baier, C., Klein, J., Kl\u00fcppelholz, S., M\u00e4rcker, S.: Computing conditional probabilities in markovian models efficiently. In: \u00c1brah\u00e1m, E., Havelund, K. (eds.) TACAS 2014 (ETAPS). LNCS, vol. 8413, pp. 515\u2013530. Springer, Heidelberg (2014)"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Br\u00e1zdil, T., Bro\u017eek, V., Etessami, K., Ku\u010dera, A., Wojtczak, D.: One-counter Markov decision processes. In: Proc. SODA, pp. 863\u2013874. SIAM (2010)","DOI":"10.1137\/1.9781611973075.70"},{"key":"19_CR6","unstructured":"Bruy\u00e8re, V., Filiot, E., Randour, M., Raskin, J.-F.: Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games. In: Proc. STACS, LIPIcs, vol. 25, pp. 199\u2013213 (2014)"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/1462153.1462154","volume":"56","author":"K Etessami","year":"2009","unstructured":"Etessami, K., Yannakakis, M.: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56(1), 1:1\u20131:66 (2009)","journal-title":"J. ACM"},{"issue":"4","key":"19_CR8","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6(4), 675\u2013695 (1977)","journal-title":"SIAM J. Comput."},{"key":"19_CR9","unstructured":"Haase, C., Kiefer, S.: The odds of staying on budget (2014). Technical Report at http:\/\/arxiv.org\/abs\/1409.8228"},{"key":"19_CR10","unstructured":"Haase, C., Kiefer, S.: The complexity of the $$K$$th largest subset problem and related problems (2015). Technical Report at http:\/\/arxiv.org\/abs\/1501.06729"},{"issue":"3","key":"19_CR11","doi-asserted-by":"crossref","first-page":"12","DOI":"10.2168\/LMCS-4(3:12)2008","volume":"4","author":"M Jurdzi\u0144ski","year":"2008","unstructured":"Jurdzi\u0144ski, M., Sproston, J., Laroussinie, F.: Model checking probabilistic timed automata with one or two clocks. Log. Meth. Comput. Sci. 4(3), 12 (2008)","journal-title":"Log. Meth. Comput. Sci."},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-540-31982-5_9","volume-title":"Foundations of Software Science and Computational Structures","author":"F Laroussinie","year":"2005","unstructured":"Laroussinie, F., Sproston, J.: Model checking durational probabilistic systems. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol. 3441, pp. 140\u2013154. Springer, Heidelberg (2005)"},{"key":"19_CR13","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons (2008)"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Randour, M., Raskin, J.-F., Sankur, O.: Percentile queries in multi-dimensional Markov decision processes. In: Proc. CAV, LNCS (2015)","DOI":"10.1007\/978-3-319-21690-4_8"},{"key":"19_CR15","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)"},{"key":"19_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/3-540-08342-1_37","volume-title":"Automata, Languages and Programming","author":"J Simon","year":"1977","unstructured":"Simon, J.: On the difference between one and many. In: Salomaa, A., Steinby, M. (eds.) ICALP 1977. LNCS, vol. 52, pp. 480\u2013491. Springer, Heidelberg (1977)"},{"issue":"5","key":"19_CR17","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":"19_CR18","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2006.08.017","volume":"369","author":"S Travers","year":"2006","unstructured":"Travers, S.: 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":"19_CR19","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)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:09:04Z","timestamp":1676945344000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}