{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:54:52Z","timestamp":1773104092302,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319893655","type":"print"},{"value":"9783319893662","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-89366-2_20","type":"book-chapter","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T23:52:34Z","timestamp":1523663554000},"page":"367-383","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Graph-Based Reductions for Reachability in Markov Decision Processes"],"prefix":"10.1007","author":[{"given":"St\u00e9phane","family":"Le Roux","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1200-4952","authenticated-orcid":false,"given":"Guillermo A.","family":"P\u00e9rez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,14]]},"reference":[{"key":"20_CR1","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., Katoen, J.-P.: Principles of Model Checking. MIT Press, New York (2008)"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Bharadwaj, S., Le Roux, S., P\u00e9rez, G.A., Topcu, U.: Reduction techniques for model checking and learning in MDPs. In: IJCAI, pp. 4273\u20134279 (2017)","DOI":"10.24963\/ijcai.2017\/597"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-319-11936-6_8","volume-title":"Automated Technology for Verification and Analysis","author":"T Br\u00e1zdil","year":"2014","unstructured":"Br\u00e1zdil, T., Chatterjee, K., Chmel\u00edk, M., Forejt, V., K\u0159et\u00ednsk\u00fd, J., Kwiatkowska, M., Parker, D., Ujma, M.: Verification of markov decision processes using learning algorithms. In: Cassez, F., Raskin, J.-F. (eds.) ATVA 2014. LNCS, vol. 8837, pp. 98\u2013114. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11936-6_8"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1137\/1.9781611973082.101","volume-title":"Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Krishnendu Chatterjee","year":"2011","unstructured":"Chatterjee, K., Henzinger, M.: Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification. In: SODA, pp. 1318\u20131336. SIAM (2011)"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Ciesinski, F., Baier, C., Gr\u00f6\u00dfer, M., Klein, J.: Reduction techniques for model checking Markov decision processes. In: QEST, pp. 45\u201354 (2008)","DOI":"10.1109\/QEST.2008.45"},{"issue":"4","key":"20_CR6","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1145\/210332.210339","volume":"42","author":"C Courcoubetis","year":"1995","unstructured":"Courcoubetis, C., Yannakakis, M.: The complexity of probabilistic verification. J. ACM 42(4), 857\u2013907 (1995)","journal-title":"J. ACM"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-44804-7_3","volume-title":"Process Algebra and Probabilistic Methods. Performance Modelling and Verification","author":"PR D\u2019Argenio","year":"2001","unstructured":"D\u2019Argenio, P.R., Jeannet, B., Jensen, H.E., Larsen, K.G.: Reachability analysis of probabilistic systems by successive refinements. In: de Alfaro, L., Gilmore, S. (eds.) PAPM-PROBMIV 2001. LNCS, vol. 2165, pp. 39\u201356. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44804-7_3"},{"key":"20_CR8","unstructured":"De Alfaro, L.: Formal verification of probabilistic systems. Ph.D. thesis, Stanford University (1997)"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/978-3-319-63390-9_31","volume-title":"Computer Aided Verification","author":"C Dehnert","year":"2017","unstructured":"Dehnert, C., Junges, S., Katoen, J.-P., Volk, M.: A Storm is coming: a modern probabilistic model checker. In: Majumdar, R., Kun\u010dak, V. (eds.) CAV 2017, Part II. LNCS, vol. 10427, pp. 592\u2013600. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63390-9_31"},{"issue":"2","key":"20_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0166-218X(97)00121-2","volume":"85","author":"T Eilam-Tzoreff","year":"1998","unstructured":"Eilam-Tzoreff, T.: The disjoint shortest paths problem. Discret. Appl. Math. 85(2), 113\u2013138 (1998)","journal-title":"Discret. Appl. Math."},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-662-44522-8_23","volume-title":"Mathematical Foundations of Computer Science 2014","author":"N Fijalkow","year":"2014","unstructured":"Fijalkow, N., Gimbert, H., Horn, F., Oualhadj, Y.: Two recursively inseparable problems for probabilistic automata. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 267\u2013278. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44522-8_23"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Fu, J., Topcu, U.: Probably approximately correct MDP learning and control with temporal logic constraints. In: RSS (2014)","DOI":"10.15607\/RSS.2014.X.039"},{"key":"20_CR14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1613\/jair.301","volume":"4","author":"LP Kaelbling","year":"1996","unstructured":"Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: a survey. JAIR 4, 237\u2013285 (1996)","journal-title":"JAIR"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Kawaguchi, K.: Bounded optimal exploration in MDP. In AAAI, pp. 1758\u20131764 (2016)","DOI":"10.1609\/aaai.v30i1.10230"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Kolobov, A., Mausam, M., Weld, D.S., Geffner, H.: Heuristic search for generalized stochastic shortest path MDPs. In: Bacchus, F., Domshlak, C., Edelkamp, S., Helmert, M. (eds.) ICAPS. AAAI (2011)","DOI":"10.1609\/icaps.v21i1.13452"},{"key":"20_CR17","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":"20_CR18","volume-title":"Markov Decision Processes","author":"ML Puterman","year":"2005","unstructured":"Puterman, M.L.: Markov Decision Processes. Wiley-Interscience, Hoboken (2005)"},{"issue":"4","key":"20_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1609\/aimag.v36i4.2577","volume":"36","author":"SJ Russell","year":"2015","unstructured":"Russell, S.J., Dewey, D., Tegmark, M.: Research priorities for robust and beneficial artificial intelligence. AI Mag. 36(4), 105\u2013114 (2015)","journal-title":"AI Mag."},{"key":"20_CR20","unstructured":"Russell, S.J., Norvig, P.: Artificial Intelligence - A Modern Approach, 3rd Int. edn., Pearson Education, London (2010)"},{"key":"20_CR21","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.5153","volume":"57","author":"M Steinmetz","year":"2016","unstructured":"Steinmetz, M., Hoffmann, J., Buffet, O.: Goal probability analysis in probabilistic planning: exploring and enhancing the state of the art. JAIR 57, 229\u2013271 (2016)","journal-title":"JAIR"},{"key":"20_CR22","first-page":"2413","volume":"10","author":"AL Strehl","year":"2009","unstructured":"Strehl, A.L., Li, L., Littman, M.L.: Reinforcement learning in finite MDPs: PAC analysis. J. Mach. Learn. Res. 10, 2413\u20132444 (2009)","journal-title":"J. Mach. Learn. Res."},{"key":"20_CR23","volume-title":"Probably Approximately Correct: Nature\u2019s Algorithms for Learning and Prospering in a Complex World","author":"L Valiant","year":"2013","unstructured":"Valiant, L.: Probably Approximately Correct: Nature\u2019s Algorithms for Learning and Prospering in a Complex World. Basic Books, New York (2013)"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-89366-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T03:34:27Z","timestamp":1693625667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-89366-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319893655","9783319893662"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-89366-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]}}}