{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T07:12:04Z","timestamp":1774681924043,"version":"3.50.1"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T00:00:00Z","timestamp":1430870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF-10-17955 and CCF-1320654"],"award-info":[{"award-number":["CCF-10-17955 and CCF-1320654"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,5,6]]},"abstract":"<jats:p>\n            We introduce Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs), which are classes of (finitely presented) countable-state MDPs and zero-sum turn-based (perfect information) stochastic games. They extend standard finite-state MDPs and stochastic games with a recursion feature. We study the decidability and computational complexity of these games under termination objectives for the two players: one player's goal is to maximize the probability of termination at a given exit, while the other player's goal is to minimize this probability. In the\n            <jats:italic>quantitative termination problems<\/jats:italic>\n            , given an RMDP (or RSSG) and probability\n            <jats:italic>p<\/jats:italic>\n            , we wish to decide whether the value of such a termination game is at least\n            <jats:italic>p<\/jats:italic>\n            (or at most\n            <jats:italic>p<\/jats:italic>\n            ); in the\n            <jats:italic>qualitative termination problem<\/jats:italic>\n            we wish to decide whether the value is 1. The important 1-exit subclasses of these models, 1-RMDPs and 1-RSSGs, correspond in a precise sense to controlled and game versions of classic stochastic models, including multitype Branching Processes and Stochastic Context-Free Grammars, where the objective of the players is to maximize or minimize the probability of termination (extinction).\n          <\/jats:p>\n          <jats:p>We provide a number of upper and lower bounds for qualitative and quantitative termination problems for RMDPs and RSSGs. We show both problems are undecidable for multi-exit RMDPs, but are decidable for 1-RMDPs and 1-RSSGs. Specifically, the quantitative termination problem is decidable in PSPACE for both 1-RMDPs and 1-RSSGs, and is at least as hard as the square root sum problem, a well-known open problem in numerical computation. We show that the qualitative termination problem for 1-RMDPs (i.e., a controlled version of branching processes) can be solved in polynomial time both for maximizing and minimizing 1-RMDPs. The qualitative problem for 1-RSSGs is in NP \u2229 coNP, and is at least as hard as the quantitative termination problem for Condon's finite-state simple stochastic games, whose complexity remains a well known open problem. Finally, we show that even for 1-RMDPs, more general (qualitative and quantitative) model-checking problems with respect to linear-time temporal properties are undecidable even for a fixed property.<\/jats:p>","DOI":"10.1145\/2699431","type":"journal-article","created":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T16:30:57Z","timestamp":1431361857000},"page":"1-69","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Recursive Markov Decision Processes and Recursive Stochastic Games"],"prefix":"10.1145","volume":"62","author":[{"given":"Kousha","family":"Etessami","sequence":"first","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225161"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"K. B. Athreya and P. E. Ney. 1972. Branching processes. Springer-Verlag.  K. B. Athreya and P. E. Ney. 1972. Branching processes. Springer-Verlag.","DOI":"10.1007\/978-3-642-65371-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050046"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1061-2"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the FSTTCS'10","author":"Br\u00e1zdil T.","unstructured":"T. Br\u00e1zdil , V. Brozek , and K. Etessami . 2010a. One-counter stochastic games . In Proceedings of the FSTTCS'10 . 108--119. T. Br\u00e1zdil, V. Brozek, and K. Etessami. 2010a. One-counter stochastic games. In Proceedings of the FSTTCS'10. 108--119."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the ICALP'11","author":"Br\u00e1zdil T.","unstructured":"T. Br\u00e1zdil , V. Brozek , K. Etessami , and T. Kucera . 2011a. Approximating the termination value of one-counter mdps and stochastic games . In Proceedings of the ICALP'11 . T. Br\u00e1zdil, V. Brozek, K. Etessami, and T. Kucera. 2011a. Approximating the termination value of one-counter mdps and stochastic games. In Proceedings of the ICALP'11."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'10)","author":"Br\u00e1zdil T.","unstructured":"T. Br\u00e1zdil , V. Brozek , K. Etessami , T. Kucera , and D. Wojtczak . 2010b. One-counter Markov decision processes . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'10) . T. Br\u00e1zdil, V. Brozek, K. Etessami, T. Kucera, and D. Wojtczak. 2010b. One-counter Markov decision processes. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'10)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11817949_24"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.02.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_12"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the SODA. 678--687","author":"Chatterjee K.","unstructured":"K. Chatterjee , L. de Alfaro , and T. A. Henzinger . 2006. The complexity of quantitative concurrent parity games . In Proceedings of the SODA. 678--687 . K. Chatterjee, L. de Alfaro, and T. A. Henzinger. 2006. The complexity of quantitative concurrent parity games. In Proceedings of the SODA. 678--687."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63519"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210339"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.720497"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.008"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 6th TACAS. 395--410","author":"de Alfaro L.","unstructured":"L. de Alfaro , M. Kwiatkowska , G. Norman , D. Parker , and R. Segala . 2000. Symbolic model checking of probabilistic processes using MTBDDs and the Kronecker representation . In Proceedings of the 6th TACAS. 395--410 . L. de Alfaro, M. Kwiatkowska, G. Norman, D. Parker, and R. Segala. 2000. Symbolic model checking of probabilistic processes using MTBDDs and the Kronecker representation. In Proceedings of the 6th TACAS. 395--410."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.009"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2005.03.033"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012904442616"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.02.015"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_57"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958042"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS). 12--21","author":"Esparza J.","unstructured":"J. Esparza , A. Ku\u010dcera , and R. Mayr . 2004. Model checking probabilistic pushdown automata . In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS). 12--21 . J. Esparza, A. Ku\u010dcera, and R. Mayr. 2004. Model checking probabilistic pushdown automata. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS). 12--21."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214030"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_27"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_58"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2009.12.009"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_72"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_52"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_28"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462154"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958052"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2159531.2159534"},{"key":"e_1_2_1_40_1","unstructured":"C. J. Everett and S. Ulam. 1948. Multiplicative systems Part I II and III. Tech. Rep. 683 690 707 Los Alamos Scientific Laboratory.  C. J. Everett and S. Ulam. 1948. Multiplicative systems Part I II and III. Tech. Rep. 683 690 707 Los Alamos Scientific Laboratory."},{"key":"e_1_2_1_41_1","volume-title":"Contributions to the Theory of Games","author":"Everett H.","unstructured":"H. Everett . 1957. Recursive games . In Contributions to the Theory of Games , vol. 3 . Annals of Mathematics Studies , no. 39. Princeton University Press, 47--78. H. Everett. 1957. Recursive games. In Contributions to the Theory of Games, vol. 3. Annals of Mathematics Studies, no. 39. Princeton University Press, 47--78."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335362"},{"key":"e_1_2_1_43_1","volume-title":"Eds","author":"Feinberg E.","year":"2002","unstructured":"E. Feinberg and A. Shwartz . Eds . 2002 . Handbook of Markov Decision Processes. Kluwer . E. Feinberg and A. Shwartz. Eds. 2002. Handbook of Markov Decision Processes. Kluwer."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"J. Filar and K. Vrieze. 1997. Competitive Markov Decision Processes. Springer.   J. Filar and K. Vrieze. 1997. Competitive Markov Decision Processes. Springer.","DOI":"10.1007\/978-1-4612-4054-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803626"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization 2nd Ed. Springer-Verlag.  M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization 2nd Ed. Springer-Verlag.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629136"},{"key":"e_1_2_1_48_1","volume-title":"The Theory of Branching Processes","author":"Harris T. E.","unstructured":"T. E. Harris . 1963. The Theory of Branching Processes . Springer-Verlag . T. E. Harris. 1963. The Theory of Branching Processes. Springer-Verlag."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2166.357214"},{"key":"e_1_2_1_50_1","unstructured":"J. E. Hopcroft and J. D. Ullman. 1979. Introduction to Automata Theory Formal Languages and Computation. Addison-Wesley.   J. E. Hopcroft and J. D. Ullman. 1979. Introduction to Automata Theory Formal Languages and Computation. Addison-Wesley."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"R. J. Horn and C. R. Johnson. 1985. Matrix Analysis. Cambridge University Press.   R. J. Horn and C. R. Johnson. 1985. Matrix Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511810817"},{"key":"e_1_2_1_52_1","volume-title":"Branching Processes with Biological Applications","author":"Jagers P.","unstructured":"P. Jagers . 1975. Branching Processes with Biological Applications . Wiley . P. Jagers. 1975. Branching Processes with Biological Applications. Wiley."},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"M. Kimmel and D. E. Axelrod. 2002. Branching Processes in Biology. Springer.  M. Kimmel and D. E. Axelrod. 2002. Branching Processes in Biology. Springer.","DOI":"10.1007\/b97371"},{"key":"e_1_2_1_54_1","first-page":"783","article-title":"The calculation of final probabilities for branching random processes","volume":"56","author":"Kolmogorov A. N.","year":"1947","unstructured":"A. N. Kolmogorov and B. A. Sevastyanov . 1947 . The calculation of final probabilities for branching random processes . Dokaldy 56 , 783 -- 786 . (Russian). A. N. Kolmogorov and B. A. Sevastyanov. 1947. The calculation of final probabilities for branching random processes. Dokaldy 56, 783--786. (Russian).","journal-title":"Dokaldy"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789069"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"G. Latouche and V. Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability.  G. Latouche and V. Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability.","DOI":"10.1137\/1.9780898719734"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00378-8"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028999140"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820050071"},{"key":"e_1_2_1_60_1","unstructured":"C. Manning and H. Sch\u00fctze. 1999. Foundations of Statistical Natural Language Processing. MIT Press.   C. Manning and H. Sch\u00fctze. 1999. Foundations of Statistical Natural Language Processing. MIT Press."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586667"},{"key":"e_1_2_1_62_1","volume-title":"Matrix-Geometric Solutions in Stochastic Models:an algorithmic approach","author":"Neuts M. F.","unstructured":"M. F. Neuts . 1981. Matrix-Geometric Solutions in Stochastic Models:an algorithmic approach . Johns Hopkins University Press . M. F. Neuts. 1981. Matrix-Geometric Solutions in Stochastic Models:an algorithmic approach. Johns Hopkins University Press."},{"key":"e_1_2_1_63_1","volume-title":"Eds","author":"Neyman A.","year":"2003","unstructured":"A. Neyman and S. Sorin . Eds . 2003 . Stochastic Games and Applications. NATO ASI Series, Kluwer . A. Neyman and S. Sorin. Eds. 2003. Stochastic Games and Applications. NATO ASI Series, Kluwer."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1969-0253756-8"},{"key":"e_1_2_1_65_1","volume-title":"Introduction to Probabilistic Automata","author":"Paz A.","unstructured":"A. Paz . 1971. Introduction to Probabilistic Automata . Academic Press . A. Paz. 1971. Introduction to Probabilistic Automata. Academic Press."},{"key":"e_1_2_1_66_1","first-page":"117","article-title":"Optimization of multitype branching processes. Manage","volume":"23","author":"Pliska S.","year":"1976","unstructured":"S. Pliska . 1976 . Optimization of multitype branching processes. Manage . Sci. 23 , 2, 117 -- 124 . S. Pliska. 1976. Optimization of multitype branching processes. Manage. Sci. 23, 2, 117--124.","journal-title":"Sci."},{"key":"e_1_2_1_67_1","volume-title":"Markov Decision Processes","author":"Puterman M. L.","unstructured":"M. L. Puterman . 1994. Markov Decision Processes . Wiley . M. L. Puterman. 1994. Markov Decision Processes. Wiley."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.4.582"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/22.23.5112"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.10.1953"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.285"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.12"},{"key":"e_1_2_1_74_1","doi-asserted-by":"crossref","unstructured":"I. Walukiewicz. 1996. Pushdown processes: games and model checking. In Computer-Aided Verification. 62--75.   I. Walukiewicz. 1996. Pushdown processes: games and model checking. In Computer-Aided Verification. 62--75.","DOI":"10.1007\/3-540-61474-5_58"},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). 66--71","author":"Wojtczak D.","unstructured":"D. Wojtczak and K. Etessami . 2007. PReMo: an analyzer for probabilistic recursive models . In Proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). 66--71 . Tool web page: http:\/\/groups.inf.ed.ac.uk\/premo\/. D. Wojtczak and K. Etessami. 2007. PReMo: an analyzer for probabilistic recursive models. In Proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). 66--71. Tool web page: http:\/\/groups.inf.ed.ac.uk\/premo\/."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699431","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,6]]},"references-count":76,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5,6]]}},"alternative-id":["10.1145\/2699431"],"URL":"https:\/\/doi.org\/10.1145\/2699431","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,6]]},"assertion":[{"value":"2011-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}