Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations Export

@article{citeulike:3986207, abstract = {We define Recursive Markov Chains (RMCs), a class of finitely presented denumerable Markov chains, and we study algorithms for their analysis. Informally, an RMC consists of a collection of finite-state Markov chains with the ability to invoke each other in a potentially recursive manner. RMCs offer a natural abstract model for probabilistic programs with procedures. They generalize, in a precise sense, a number of well-studied stochastic models, including Stochastic Context-Free Grammars (SCFG) and Multi-Type Branching Processes (MT-BP).}, address = {New York, NY, USA}, author = {Etessami, Kousha and Yannakakis, Mihalis}, citeulike-article-id = {3986207}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1462153.1462154}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1462153.1462154}, doi = {10.1145/1462153.1462154}, issn = {0004-5411}, journal = {J. ACM}, keywords = {markov}, number = {1}, pages = {1--66}, posted-at = {2009-01-30 18:55:25}, priority = {3}, publisher = {ACM}, title = {Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations}, url = {http://dx.doi.org/10.1145/1462153.1462154}, volume = {56}, year = {2009} }

TY - JOUR ID - citeulike:3986207 L3 - citeulike-article-id:3986207 N2 - We define Recursive Markov Chains (RMCs), a class of finitely presented denumerable Markov chains, and we study algorithms for their analysis. Informally, an RMC consists of a collection of finite-state Markov chains with the ability to invoke each other in a potentially recursive manner. RMCs offer a natural abstract model for probabilistic programs with procedures. They generalize, in a precise sense, a number of well-studied stochastic models, including Stochastic Context-Free Grammars (SCFG) and Multi-Type Branching Processes (MT-BP). IS - 1 JF - J. ACM SN - 0004-5411 AD - New York, NY, USA EP - 66 TI - Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations PB - ACM VL - 56 SP - 1 KW - markov AU - Etessami, Kousha AU - Yannakakis, Mihalis PY - 2009/// UR - http://dx.doi.org/10.1145/1462153.1462154 ER -