Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Recursive Markov Decison Processes and Recursive Stochastic Games
Authors: Kousha Etessami ; Mihalis Yannakakis
Date: 2005
Publication Title:Proceedings of ICALP 2005 (International Colloquium on Automata, Languages and Programming)
Publication Type:Conference Paper Publication Status:Published
Volume No:3580 Page Nos:891-903
DOI:10.1007/11523468_72 ISBN/ISSN:1611-3349
We introduce Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs), and study the decidability and complexity of algorithms for their analysis and verification. These models extend Recursive Markov Chains (RMCs), introduced in [EY05a, EY05b] as a natural model for verification of probabilistic procedural programs and related systems involving both recursion and probabilistic behavior. RMCs define a class of denumerable Markov chains with a rich theory generalizing that of stochastic context-free grammars and multi-type branching processes, and they are also intimately related to probabilistic pushdown systems. RMDPs & RSSGs extend RMCs with one controller or two adversarial players, respectively. Such extensions are useful for modeling nondeterministic and concurrent behavior, as well as modeling a system s interactions with an environment. We provide upper and lower bounds for deciding, given an RMDP (or RSSG) A and probability p, whether player 1 has a strategy to force termination at a desired exit with probability at least p. We also address qualitative termination, where p=1, and model checking questions.
Links To Paper
1st Link
Bibtex format
author = { Kousha Etessami and Mihalis Yannakakis },
title = {Recursive Markov Decison Processes and Recursive Stochastic Games},
book title = {Proceedings of ICALP 2005 (International Colloquium on Automata, Languages and Programming)},
publisher = {Springer},
year = 2005,
volume = {3580},
pages = {891-903},
doi = {10.1007/11523468_72},
url = {,72,118;journal,252,2376;linkingpublicationresults,1:105633,1},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh