- Abstract:
-
We introduce and study Recursive Markov Chains (RMCs), which extend ordinary finite state Markov chains with the ability to invoke other Markov chains in a potentially recursive manner. They offer a natural abstract model for probabilistic programs with procedures, and are a probabilistic version of Recursive State Machines. RMCs generalize Stochastic Context-Free Grammars (SCFG) and multi-type Branching Processes, and are intimately related to Probabilistic Pushdown Systems. We focus here on termination and reachability analysis for RMCs. We present both positive and negative results for the general class of RMCs, as well as for important subclasses including SCFGs.
- Links To Paper
- 1st Link
- Bibtex format
- @InProceedings{EDI-INF-RR-0603,
- author = {
Kousha Etessami
and Mihalis Yannakakis
},
- title = {Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations},
- book title = {Proceedings of STACS 2005 (Symposium on Theoretical Aspects of Computer Science)},
- publisher = {Springer},
- year = 2005,
- month = {Jan},
- volume = {3404},
- pages = {340-352},
- doi = {10.1007/b106485},
- url = {http://springerlink.metapress.com/(ed15nq451amesb55xwybywrs)/app/home/contribution.asp?referrer=parent&backto=issue,28,57;journal,423,2341;linkingpublicationresults,1:105633,1},
- }
|
