×

zbMATH — the first resource for mathematics

Recursive Markov decision processes and recursive stochastic games. (English) Zbl 1333.91005

MSC:
91A15 Stochastic games, stochastic differential games
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
68Q25 Analysis of algorithms and problem complexity
68Q42 Grammars and rewriting systems
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
90C40 Markov and semi-Markov decision processes
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen. 2009. On the complexity of numerical analysis. SIAM J. Comput. 38, 5, 1987–2006. Earlier conference version appeared in Proc., 21st IEEE Conference on Computational Complexity.
[2] R. Alur, M. Benedikt, K. Etessami, P. Godefroid, T. Reps, and M. Yannakakis. 2005. Analysis of recursive state machines. ACM Trans. Program. Lang. Syst. 27, 4, 786–818. · Zbl 05459217 · doi:10.1145/1075382.1075387
[3] R. Alur, C. Courcoubetis, and M. Yannakakis. 1995. Distinguishing tests for nondeterministic and probabilistic machines. In Proceedings of the 20th STOC. 363–372. · Zbl 0978.68522 · doi:10.1145/225058.225161
[4] K. B. Athreya and P. E. Ney. 1972. Branching processes. Springer-Verlag. · Zbl 0259.60002 · doi:10.1007/978-3-642-65371-1
[5] C. Baier and M. Kwiatkowska. 1998. Model checking for a probabilistic branching time logic with fairness. Distrib. Comput. 11, 3, 125–155. · doi:10.1007/s004460050046
[6] V. Blondel and V. Canterini. 2003. Undecidable problems for probabilistic automata of fixed dimension. Theory Comput. Syst. 36, 231–245. · Zbl 1039.68061 · doi:10.1007/s00224-003-1061-2
[7] T. Brázdil, V. Brozek, and K. Etessami. 2010a. One-counter stochastic games. In Proceedings of the FSTTCS’10. 108–119.
[8] T. Brázdil, 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.
[9] T. Brázdil, 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).
[10] T. Brázdil, V. Brozek, V. Forejt, and A. Kucera. 2006. Reachability in recursive Markov decision processes. In Proceedings of the 17th International CONCUR. 358–374.
[11] T. Brázdil, V. Brozek, A. Kucera, and J. Obdrzálek. 2011b. Qualitative reachability in stochastic bpa games. Inf. Computat. 209, 8, 1160–1183.
[12] T. Brázdil, A. Kučcera, and O. Stražzovský 2005. Decidability of temporal properties of probabilistic pushdown automata. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS).
[13] J. Canny. 1988. Some algebraic and geometric computations in PSPACE. In Proceedings of the 20th ACM Symposium on Theory of Computing (STOC). 460–467. · doi:10.1145/62212.62257
[14] K. Chatterjee, L. de Alfaro, and T. A. Henzinger. 2006. The complexity of quantitative concurrent parity games. In Proceedings of the SODA. 678–687. · Zbl 1192.68430 · doi:10.1145/1109557.1109631
[15] A. Condon. 1992. The complexity of stochastic games. Inf. Comput. 96, 2, 203–224. · Zbl 0756.90103 · doi:10.1016/0890-5401(92)90048-K
[16] A. Condon and R. Lipton. 1989. The complexity of space bounded interactive proofs. In Proceedings of the 30th IEEE FOCS. · doi:10.1109/SFCS.1989.63519
[17] C. Courcoubetis and M. Yannakakis. 1995. The complexity of probabilistic verification. J. ACM 42, 4, 857–907. · Zbl 0885.68109 · doi:10.1145/210332.210339
[18] C. Courcoubetis and M. Yannakakis. 1998. Markov decision processes and regular events. IEEE Trans. Automat. Cont. 43, 10, 1399–1418. · Zbl 0954.90061 · doi:10.1109/9.720497
[19] L. de Alfaro, T. A. Henzinger, and O. Kupferman. 2007. Concurrent reachability games. Theoret. Comput. Sci. 386, 3, 188–217. · Zbl 1154.91306 · doi:10.1016/j.tcs.2007.07.008
[20] 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. · Zbl 0960.68109 · doi:10.1007/3-540-46419-0_27
[21] L. de Alfaro and R. Majumdar. 2004. Quantitative solution of omega-regular games. J. Comput. Syst. Sci. 68, 2, 374–397. · Zbl 1093.91001 · doi:10.1016/j.jcss.2003.07.009
[22] E. Denardo and U. Rothblum. 2005. Totally expanding multiplicative systems. Lin. Alg. Appl. 406, 142–158. · Zbl 1078.15017 · doi:10.1016/j.laa.2005.03.033
[23] E. V. Denardo and U. G. Rothblum. 2006. A turnpike theorem for a risk-sensitive markov decision process with stopping. SIAM J. Control Optimiz. 45, 2, 414–431. · Zbl 1151.90571 · doi:10.1137/S0363012904442616
[24] A. Ehrenfeucht and J. Mycielski. 1979. Positional strategies for mean payoff games. Int. J. Game Theory 8, 109–113. · Zbl 0499.90098 · doi:10.1007/BF01768705
[25] E. A. Emerson and C. S. Jutla. 1991. Tree automata, mu-calculus, and determinacy. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science (FOCS). 368–377. · doi:10.1109/SFCS.1991.185392
[26] J. Esparza, A. Gaiser, and S. Kiefer. 2013. A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars. Inf. Process. Lett. 113, 10–11, 381–385. · Zbl 1371.68202 · doi:10.1016/j.ipl.2013.02.015
[27] J. Esparza, T. Gawlitza, S. Kiefer, and H. Seidl. 2008. Approximative methods for monotone systems of min-max-polynomial equations. In Proceedings of the ICALP (1). 698–710. · Zbl 1153.65337 · doi:10.1007/978-3-540-70575-8_57
[28] J. Esparza, S. Kiefer, and M. Luttenberger. 2010. Computing the least fixed point of positive polynomial systems. SIAM J. Comput. 39, 6, 2282–2335. · Zbl 1213.65076 · doi:10.1137/090749591
[29] J. Esparza, A. Kučcera, and R. Mayr. 2004. Model checking probabilistic pushdown automata. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS). 12–21.
[30] K. Etessami, A. Stewart, and M. Yannakakis. 2012a. Polynomial-time algorithms for multi-type branching processes and stochastic context-free grammars. In Proceedings of the 44th ACM STOC. (Full version is available at ArXiv:1201.2374.) · Zbl 1286.68188
[31] K. Etessami, A. Stewart, and M. Yannakakis. 2012b. Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP). 314–326. (Full version at ArXiv:1202.4798.) · Zbl 1272.68458
[32] K. Etessami, D. Wojtczak, and M. Yannakakis. 2008. Recursive stochastic games with positive rewards. In Proceedings of the 35th ICALP. 71–723. · Zbl 1153.91328 · doi:10.1007/978-3-540-70575-8_58
[33] K. Etessami, D. Wojtczak, and M. Yannakakis. 2010. Quasi-birth-death processes, tree-like QBDs, probabilistic 1-counter automata, and pushdown systems. Perform. Eval. 67, 9, 837–857. (conference version appeared in QEST’08.)
[34] K. Etessami and M. Yannakakis. 2005. Recursive Markov decision processes and recursive stochastic games. In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP). 891–903. · Zbl 1085.68089 · doi:10.1007/11523468_72
[35] K. Etessami and M. Yannakakis. 2006. Efficient qualitative analysis of classes of recursive Markov decision processes and simple stochastic games. In Proceedings of the 23rd STACS’06. Springer. · Zbl 1136.90499 · doi:10.1007/11672142_52
[36] K. Etessami and M. Yannakakis. 2008. Recursive concurrent stochastic games. Logi. Meth. Comput. Sci. 4, 4. (Conference version appeared in ICALP’06.) · Zbl 1161.68619
[37] K. Etessami and M. Yannakakis. 2009. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56, 1. · Zbl 1325.68091 · doi:10.1145/1462153.1462154
[38] K. Etessami and M. Yannakakis. 2010. On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39, 6, 2531–2597. (Conference version appeared in Proceedings of the 48th IEEE Symposium on Foundations of Computer Science (FOCS’07.) · Zbl 1204.91003
[39] K. Etessami and M. Yannakakis. 2012. Model checking of recursive probabilistic systems. ACM Trans. Computat. Logic 13. · Zbl 1351.68159
[40] C. J. Everett and S. Ulam. 1948. Multiplicative systems, Part I, II, and III. Tech. Rep. 683,690,707, Los Alamos Scientific Laboratory. · Zbl 0032.29104
[41] 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. · Zbl 0078.32802
[42] R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins. 2000. Random walks with ”back buttons” (extended abstract). In Proceedings of the ACM Symposium on Theory of Computing (STOC). 484–493. · Zbl 1296.60191 · doi:10.1145/335305.335362
[43] E. Feinberg and A. Shwartz. Eds. 2002. Handbook of Markov Decision Processes. Kluwer. · Zbl 0979.90001 · doi:10.1007/978-1-4615-0805-2
[44] J. Filar and K. Vrieze. 1997. Competitive Markov Decision Processes. Springer. · Zbl 0934.91002
[45] M. R. Garey, R. L. Graham, and D. S. Johnson. 1976. Some NP-complete geometric problems. In Proceedings of the 8th ACM Symposium on Theory of Computing (STOC). 10–22. · Zbl 0377.68036 · doi:10.1145/800113.803626
[46] M. Grötschel, L. Lovász, and A. Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization 2nd Ed. Springer-Verlag.
[47] P. Haccou, P. Jagers, and V. A. Vatutin. 2005. Branching Processes: Variation, Growth, and Extinction of Populations. Cambridge University Press. · Zbl 1118.92001 · doi:10.1017/CBO9780511629136
[48] T. E. Harris. 1963. The Theory of Branching Processes. Springer-Verlag. · Zbl 0117.13002 · doi:10.1007/978-3-642-51866-9
[49] S. Hart, M. Sharir, and A. Pnueli. 1983. Termination of probabilistic concurrent programs. ACM Trans. Prog. Languages and Systems 5, 3, 356–380. · Zbl 0511.68009 · doi:10.1145/2166.357214
[50] J. E. Hopcroft and J. D. Ullman. 1979. Introduction to Automata Theory, Formal Languages and Computation. Addison-Wesley. · Zbl 0426.68001
[51] R. J. Horn and C. R. Johnson. 1985. Matrix Analysis. Cambridge University Press. · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[52] P. Jagers. 1975. Branching Processes with Biological Applications. Wiley. · Zbl 0356.60039
[53] M. Kimmel and D. E. Axelrod. 2002. Branching Processes in Biology. Springer. · Zbl 0994.92001 · doi:10.1007/b97371
[54] A. N. Kolmogorov and B. A. Sevastyanov. 1947. The calculation of final probabilities for branching random processes. Dokaldy 56, 783–786. (Russian).
[55] M. Kwiatkowska. 2003. Model checking for probability and time: from theory to practice. In Proceedings of the 18th IEEE LICS. 351–360 · doi:10.1109/LICS.2003.1210075
[56] G. Latouche and V. Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM Series on Statistics and Applied Probability. · Zbl 0922.60001 · doi:10.1137/1.9780898719734
[57] O. Madani, S. Hanks, and A. Condon. 2003. On the undecidability of probabilistic planning and related stochastic optimization problems. Artif. Intell. 147, 1, 5–34. · Zbl 1082.68806 · doi:10.1016/S0004-3702(02)00378-8
[58] K. Mahler. 1964. An inequality for the discriminant of a polynomial. Mich. Math J. 11, 257–262. · Zbl 0135.01702 · doi:10.1307/mmj/1028999140
[59] A. Maitra and W. Sudderth. 1998. Finitely additive stochastic games with Borel measurable payoffs. Internat. J. Game Theory 27, 2, 257–267. · Zbl 0947.91013 · doi:10.1007/s001820050071
[60] C. Manning and H. Schütze. 1999. Foundations of Statistical Natural Language Processing. MIT Press.
[61] D. A. Martin. 1998. Determinacy of Blackwell games. J. Symb. Logic 63, 4, 1565–1581. · Zbl 0926.03071 · doi:10.2307/2586667
[62] M. F. Neuts. 1981. Matrix-Geometric Solutions in Stochastic Models:an algorithmic approach. Johns Hopkins University Press. · Zbl 0469.60002
[63] A. Neyman and S. Sorin. Eds. 2003. Stochastic Games and Applications. NATO ASI Series, Kluwer. · doi:10.1007/978-94-010-0189-2
[64] D. Ornstein. 1969. On the existence of stationary optimal strategies. Proc. Amer. Math. Soc. 20, 563–569. · Zbl 0181.47103 · doi:10.1090/S0002-9939-1969-0253756-8
[65] A. Paz. 1971. Introduction to Probabilistic Automata. Academic Press. · Zbl 0234.94055
[66] S. Pliska. 1976. Optimization of multitype branching processes. Manage. Sci. 23, 2, 117–124. · Zbl 0345.90043 · doi:10.1287/mnsc.23.2.117
[67] M. L. Puterman. 1994. Markov Decision Processes. Wiley. · doi:10.1002/9780470316887
[68] J. Renegar. 1992. On the computational complexity and geometry of the first-order theory of the reals, parts I-III. J. Symbol. Computat. 13, 3, 255–352. · Zbl 0763.68042 · doi:10.1016/S0747-7171(10)80003-3
[69] U. Rothblum and P. Whittle. 1982. Growth optimality for branching Markov decision chains. Math. Oper. Res. 7, 4, 582–601. · Zbl 0498.90082 · doi:10.1287/moor.7.4.582
[70] Y. Sakakibara, M. Brown, R. Hughey, I. Mian, K. Sjolander, R. Underwood, and D. Haussler. 1994. Stochastic context-free grammars for tRNA modeling. Nucleic Acids Rese. 22, 23, 5112–5120. · doi:10.1093/nar/22.23.5112
[71] L. Shapley. 1953. Stochastic games. Proc. Nat. Acad. Sci. 39, 1095–1100. · Zbl 0051.35805 · doi:10.1073/pnas.39.10.1095
[72] A. Tarski. 1955. A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 5, 285–309. · Zbl 0064.26004 · doi:10.2140/pjm.1955.5.285
[73] M. Vardi. 1985. Automatic verification of probabilistic concurrent finite-state programs. In Proceedings of the 26th IEEE FOCS. 327–338. · doi:10.1109/SFCS.1985.12
[74] I. Walukiewicz. 1996. Pushdown processes: games and model checking. In Computer-Aided Verification. 62–75.
[75] 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/.
[76] U. Zwick and M. Paterson. 1996. The complexity of mean payoff games on graphs. Theoret. Comput. Sci. 158, 1–2, 343–359. · Zbl 0871.68138 · doi:10.1016/0304-3975(95)00188-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.