{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T23:50:44Z","timestamp":1777765844503,"version":"3.51.4"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031974380","type":"print"},{"value":"9783031974397","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"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":[[2026]]},"DOI":"10.1007\/978-3-031-97439-7_3","type":"book-chapter","created":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T11:04:01Z","timestamp":1756551841000},"page":"70-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decisiveness for\u00a0Countable MDPs and\u00a0Insights for\u00a0NPLCSs and\u00a0POMDPs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9957-5394","authenticated-orcid":false,"given":"Nathalie","family":"Bertrand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2823-0911","authenticated-orcid":false,"given":"Patricia","family":"Bouyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5763-3130","authenticated-orcid":false,"given":"Thomas","family":"Brihaye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paulin","family":"Fournier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5834-1068","authenticated-orcid":false,"given":"Pierre","family":"Vandenhove","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,30]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., Ben\u00a0Henda, N., Mayr, R.: Decisive Markov chains. Logical Methods Comput. Sci. 3(4:7), 1\u201332 (2007). https:\/\/doi.org\/10.2168\/LMCS-3(4:7)2007","DOI":"10.2168\/LMCS-3(4:7)2007"},{"issue":"2","key":"3_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/J.IC.2005.05.008","volume":"202","author":"PA Abdulla","year":"2005","unstructured":"Abdulla, P.A., Bertrand, N., Rabinovich, A., Schnoebelen, P.: Verification of probabilistic systems with faulty communication. Inf. Comput. 202(2), 141\u2013165 (2005). https:\/\/doi.org\/10.1016\/J.IC.2005.05.008","journal-title":"Inf. Comput."},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., Clemente, L., Mayr, R., Sandberg, S.: Stochastic parity games on lossy channel systems. Logical Methods Comput. Sci. 10(4) (2014). https:\/\/doi.org\/10.2168\/LMCS-10(4:21)2014","DOI":"10.2168\/LMCS-10(4:21)2014"},{"key":"3_CR4","unstructured":"de\u00a0Alfaro, L.: Formal Verification of Probabilistic Systems. Ph.D. thesis, Stanford University, Stanford, CA (1997). http:\/\/i.stanford.edu\/pub\/cstr\/reports\/cs\/tr\/98\/1601\/CS-TR-98-1601.pdf"},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.ipl.2005.09.011","volume":"97","author":"C Baier","year":"2006","unstructured":"Baier, C., Bertrand, N., Schnoebelen, P.: A note on the attractor-property of infinite-state Markov chains. Inf. Process. Lett. 97(2), 58\u201363 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2005.09.011","journal-title":"Inf. Process. Lett."},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Baier, C., Bertrand, N., Schnoebelen, Ph.: Verifying nondeterministic probabilistic channel systems against $$\\omega $$-regular linear-time properties. ACM Trans. Comput. Logic 9(1) (2007). https:\/\/doi.org\/10.1145\/1297658.1297663","DOI":"10.1145\/1297658.1297663"},{"key":"3_CR7","unstructured":"Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press (2008)"},{"key":"3_CR8","doi-asserted-by":"publisher","unstructured":"Barbot, B., Bouyer, P., Haddad, S.: Beyond decisiveness of infinite Markov chains. In: Proceedings of 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). LIPIcs, vol.\u00a0323, pp. 8:1\u20138:22. Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2024.8","DOI":"10.4230\/LIPIcs.FSTTCS.2024.8"},{"key":"3_CR9","unstructured":"Bertrand, N., Bouyer, P., Brihaye, T., Fournier, P., Vandenhove, P.: Decisiveness for countable MDPs and insights for NPLCSs and POMDPs. CoRR abs\/2008.10426 (2020). https:\/\/arxiv.org\/abs\/2008.10426"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/3-540-36576-1_8","volume-title":"Foundations of Software Science and Computation Structures","author":"N Bertrand","year":"2003","unstructured":"Bertrand, N., Schnoebelen, P.: Model checking lossy channels systems is probably decidable. In: Gordon, A.D. (ed.) FoSSaCS 2003. LNCS, vol. 2620, pp. 120\u2013135. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-36576-1_8"},{"key":"3_CR11","doi-asserted-by":"publisher","unstructured":"Bertrand, N., Schnoebelen, Ph.: Solving stochastic B\u00fcchi games on infinite arenas with a finite attractor. In: Proceedings of 11th International Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2013). EPTCS, vol.\u00a0117, pp. 116\u2013131 (2013). https:\/\/doi.org\/10.4204\/EPTCS.117.8","DOI":"10.4204\/EPTCS.117.8"},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Br\u00e1zdil, T., Brozek, V., Etessami, K.: One-counter stochastic games. In: Proceedings IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201910). LIPIcs, vol.\u00a08, pp. 108\u2013119. Leibniz-Zentrum f\u00fcr Informatik (2010). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2010.108","DOI":"10.4230\/LIPIcs.FSTTCS.2010.108"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/978-3-642-22012-8_26","volume-title":"Automata, Languages and Programming","author":"T Br\u00e1zdil","year":"2011","unstructured":"Br\u00e1zdil, T., Bro\u017eek, V., Etessami, K., Ku\u010dera, A.: Approximating the termination value of one-counter MDPs and stochastic games. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 332\u2013343. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22012-8_26"},{"issue":"8","key":"3_CR14","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1016\/J.IC.2011.02.002","volume":"209","author":"T Br\u00e1zdil","year":"2011","unstructured":"Br\u00e1zdil, T., Brozek, V., Kucera, A., Obdrz\u00e1lek, J.: Qualitative reachability in stochastic BPA games. Inf. Comput. 209(8), 1160\u20131183 (2011). https:\/\/doi.org\/10.1016\/J.IC.2011.02.002","journal-title":"Inf. Comput."},{"key":"3_CR15","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., et al.: 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"},{"issue":"5","key":"3_CR16","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1016\/J.JCSS.2016.02.009","volume":"82","author":"K Chatterjee","year":"2016","unstructured":"Chatterjee, K., Chmelik, M., Tracol, M.: What is decidable about partially observable Markov decision processes with $$\\omega $$-regular objectives. J. Comput. Syst. Sci. 82(5), 878\u2013911 (2016). https:\/\/doi.org\/10.1016\/J.JCSS.2016.02.009","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Inf. Comput. 96(2), 203\u2013224 (1992). https:\/\/doi.org\/10.1016\/0890-5401(92)90048-K","journal-title":"Inf. Comput."},{"key":"3_CR18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1007\/978-3-319-63390-9_31","volume-title":"CAV 2017","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. LNCS, vol. 10427, pp. 592\u2013600. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63390-9_31"},{"issue":"9","key":"3_CR19","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1016\/j.peva.2009.12.009","volume":"67","author":"K Etessami","year":"2010","unstructured":"Etessami, K., Wojtczak, D., Yannakakis, M.: Quasi-birth-death processes, tree-like QBDs, probabilistic $$1$$-counter automata, and pushdown systems. Perform. Eval. 67(9), 837\u2013857 (2010). https:\/\/doi.org\/10.1016\/j.peva.2009.12.009","journal-title":"Perform. Eval."},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. Logical Methods Comput. Sci. 4(4) (2008). https:\/\/doi.org\/10.2168\/LMCS-4(4:7)2008","DOI":"10.2168\/LMCS-4(4:7)2008"},{"issue":"4","key":"3_CR21","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/3157831.3157833","volume":"4","author":"N Fijalkow","year":"2017","unstructured":"Fijalkow, N.: Undecidability results for probabilistic automata. ACM SIGLOG News 4(4), 10\u201317 (2017). https:\/\/doi.org\/10.1145\/3157831.3157833","journal-title":"ACM SIGLOG News"},{"key":"3_CR22","doi-asserted-by":"publisher","unstructured":"Finkel, A., Haddad, S., Ye, L.: About decisiveness of dynamic probabilistic models. In: Proceedings of 34th International Conference on Concurrency Theory (CONCUR\u201923). LIPIcs, vol.\u00a0279, pp. 14:1\u201314:17. Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.CONCUR.2023.14","DOI":"10.4230\/LIPICS.CONCUR.2023.14"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/978-3-642-14162-1_44","volume-title":"Automata, Languages and Programming","author":"H Gimbert","year":"2010","unstructured":"Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: decidable and undecidable problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 527\u2013538. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14162-1_44"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.tcs.2016.12.003","volume":"735","author":"S Haddad","year":"2018","unstructured":"Haddad, S., Monmege, B.: Interval iteration algorithm for MDPs and IMDPs. Theoret. Comput. Sci. 735, 111\u2013131 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2016.12.003","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR25","doi-asserted-by":"publisher","unstructured":"Iyer, S., Narasimha, M.: Probabilistic lossy channel systems. In: Proceedings 7th International Conference on Theory and Practice of Software Development (TAPSOFT\u201997). Lecture Notes in Computer Science, vol.\u00a01214, pp. 667\u2013681. Springer, Cham (1997). https:\/\/doi.org\/10.1007\/BFB0030633","DOI":"10.1007\/BFB0030633"},{"issue":"1\u20132","key":"3_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0004-3702(98)00023-X","volume":"101","author":"L Kaelbling","year":"1998","unstructured":"Kaelbling, L., Littman, M.L., Cassandra, A.R.: Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1\u20132), 99\u2013134 (1998). https:\/\/doi.org\/10.1016\/S0004-3702(98)00023-X","journal-title":"Artif. Intell."},{"key":"3_CR27","doi-asserted-by":"publisher","unstructured":"Kiefer, S., Mayr, R., Shirmohammadi, M., Totzke, P., Wojtczak, D.: How to play in infinite MDPs (invited talk). In: Czumaj, A., Dawar, A., Merelli, E. (eds.) Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). LIPIcs, vol.\u00a0168, pp. 3:1\u20133:18. Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2020.3","DOI":"10.4230\/LIPICS.ICALP.2020.3"},{"key":"3_CR28","doi-asserted-by":"publisher","unstructured":"Kiefer, S., Mayr, R., Shirmohammadi, M., Wojtczak, D.: Parity objectives in countable MDPs. In: Proceedings of 32th Annual Symposium on Logic in Computer Science (LICS 2017), pp. 1\u201311. IEEE Computer Society Press (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005100","DOI":"10.1109\/LICS.2017.8005100"},{"key":"3_CR29","volume-title":"Lectures in Game Theory for Computer Scientists","author":"A Kucera","year":"2011","unstructured":"Kucera, A.: Lectures in Game Theory for Computer Scientists. Cambridge University Press, Turn-Based Stochastic Games (2011). chap"},{"key":"3_CR30","doi-asserted-by":"publisher","unstructured":"Kucera, A., Esparza, J., Mayr, R.: Model checking probabilistic pushdown automata. Logical Methods Comput. Sci. 2(1) (2006). https:\/\/doi.org\/10.2168\/LMCS-2(1:2)2006","DOI":"10.2168\/LMCS-2(1:2)2006"},{"key":"3_CR31","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":"3_CR32","unstructured":"Madani, O., Hanks, S., Condon, A.: On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems. In: Hendler, J., Subramanian, D. (eds.) Proc. 16th National Conference on Artificial Intelligence and Eleventh Conference on Innovative Applications of Artificial Intelligence, pp. 541\u2013548. AAAI Press \/ The MIT Press (1999)"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Ornstein, D.: On the existence of stationary optimal strategies. Proc. Am. Math. Soc. 20(2), 563\u2013569 (1969). http:\/\/www.jstor.org\/stable\/2035700","DOI":"10.1090\/S0002-9939-1969-0253756-8"},{"key":"3_CR34","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press (1971)"},{"key":"3_CR35","doi-asserted-by":"publisher","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics, Wiley, 1st edn. (1994). https:\/\/doi.org\/10.1002\/9780470316887","DOI":"10.1002\/9780470316887"},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"Sericola, B.: Markov Chains: Theory, Algorithms and Applications. Wiley, Hoboken (2013)","DOI":"10.1002\/9781118731543"},{"issue":"10","key":"3_CR37","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"LS Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. 39(10), 1095\u20131100 (1953). https:\/\/doi.org\/10.1073\/pnas.39.10.1095","journal-title":"Proc. Natl. Acad. Sci."}],"container-title":["Lecture Notes in Computer Science","Principles of Formal Quantitative Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-97439-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T15:29:59Z","timestamp":1777476599000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-97439-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,30]]},"ISBN":["9783031974380","9783031974397"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-97439-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,30]]},"assertion":[{"value":"30 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}