The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
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). We focus on algorithms for reachability and termination analysis for RMCs: what is the probability that an RMC started from a given state reaches another target state, or that it terminates? These probabilities are in general irrational, and they arise as (least) fixed point solutions to certain (monotone) systems of nonlinear equations associated with RMCs. We address both the qualitative problem of determining whether the probabilities are 0, 1 or in-between, and the quantitative problems of comparing the probabilities with a given bound, or approximating them to desired precision. We show that all these problems can be solved in PSPACE using a decision procedure for the Existential Theory of Reals. We provide a more practical algorithm, based on a decomposed version of multi-variate Newton's method, and prove that it always converges monotonically to the desired probabilities. We show this method applies more generally to any monotone polynomial system. We obtain polynomial-time algorithms for various special subclasses of RMCs. Among these: for SCFGs and MT-BPs (equivalently, for 1-exit RMCs) the qualitative problem can be solved in P-time; for linearly recursive RMCs the probabilities are rational and can be computed exactly in P-time. We show that our PSPACE upper bounds cannot be substantially improved without a breakthrough on long standing open problems: the square-root sum problem and an arithmetic circuit decision problem that captures P-time on the unit-cost rational arithmetic RAM model. We show that these problems reduce to the qualitative problem and to the approximation problem (to within any nontrivial error) for termination probabilities of general RMCs, and to the quantitative decision problem for termination (extinction) of SCFGs (MT-BPs).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Introduction to automata theory, languages and computation
(1981) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(81)90068-9 · Cited by 10,699
Horn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280
Foundations of statistical natural language processing
Manning, C. D., & Schütze, H. (1999) · Cited by 9,816
Gantmacher, F. R. (1984) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 8,520
Iterative Solution of Nonlinear Equations in Several Variables
Ortega, J. M., & Rheinboldt, W. C. (2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719468 · Cited by 6,860
Introduction to Numerical Analysis.
Froberg, C.-E., Stoer, J., & Bulirsch, R. (1981) · Mathematics of Computation · doi:10.2307/2007454 · Cited by 5,463
A First Course in Stochastic Processes
(1975) · Elsevier eBooks · doi:10.1016/c2009-1-28569-8 · Cited by 3,890
Biological sequence analysis probabilistic models of proteins and nucleic acids
Durbin, R. M., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cited by 3,565
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach.
Heyde, C. C., & Neuts, M. F. (1982) · Journal of the American Statistical Association · doi:10.2307/2287748 · Cited by 3,248
Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids
Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511790492 · Cited by 3,246
Jacob, M. (1989) · Health Education Journal · doi:10.1177/001789698904800401 · Cited by 3,090
The Theory of Branching Processes
Ney, P. E. (1965) · Technometrics · doi:10.1080/00401706.1965.10490235 · Cited by 2,404
Athreya, K. B., & Ney, P. E. (1972) · Springer eBooks · doi:10.1007/978-3-642-65371-1 · Cited by 1,665
Introduction to Numerical Analysis
Stoer, J., & Bulirsch, R. Z. (1993) · Texts in applied mathematics · doi:10.1007/978-1-4757-2272-7 · Cited by 1,277
Complexity and real computation
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6275c · Cited by 1,228
Complexity and Real Computation
Blum, L., Cucker, F., Shub, M., & Smale, S. (1998) · Springer eBooks · doi:10.1007/978-1-4612-0701-6 · Cited by 869
Branching Processes with Biological Applications
Radcliffe, J., & Jagers, P. (1977) · International Statistical Review / Revue Internationale de Statistique · doi:10.2307/1403323 · Cited by 848
Some algebraic and geometric computations in PSPACE
Canny, J. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62257 · Cited by 572
The Theory of Branching Processes.
Bartlett, M. S., & Harris, T. E. (1964) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2343607 · Cited by 483
Some NP-complete geometric problems
Garey, M. R., Graham, R. L., & Johnson, D. S. (1976) · Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76 · doi:10.1145/800113.803626 · Cited by 400
Branching Processes in Biology
Kimmel, M., & Axelrod, D. E. (2015) · Interdisciplinary Applied Mathematics · doi:10.1007/978-1-4939-1559-0 · Cited by 387
Stochastic context-free grammers for tRNA modeling
Sakakibara, Y., Brown, M., Hughey, R., Mian, I. S., Sjölander, K., Underwood, R. C., & Haussler, D. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.23.5112 · Cited by 383
Program analysis via graph reachability
Reps, T. (1998) · Information and Software Technology · doi:10.1016/s0950-5849(98)00093-7 · Cited by 357
Branching Processes: Variation, Growth, and Extinction of Populations
Haccou, P., Jagers, P., & Vatutin, V. A. (2005) · Cambridge University Press eBooks · doi:10.1017/cbo9780511629136 · Cited by 316
Branching Processes in Biology
Kimmel, M., & Axelrod, D. E. (2002) · Interdisciplinary Applied Mathematics · doi:10.1007/b97371 · Cited by 305
A First Course in Stochastic Processes.
Port, S., & Karlin, S. (1968) · The American Mathematical Monthly · doi:10.2307/2314395 · Cited by 266
On the Complexity of Nash Equilibria and Other Fixed Points
Etessami, K., & Yannakakis, M. (2010) · SIAM Journal on Computing · doi:10.1137/080720826 · Cited by 249
Self-citationApplying Probability Measures to Abstract Languages
Booth, T. L., & Thompson, R. A. (1973) · IEEE Transactions on Computers · doi:10.1109/t-c.1973.223746 · Cited by 228
Albers, S., & Marion, J.-Y. (2009) · Publication Server of Goethe University Frankfurt am Main (Goethe University Frankfurt) · doi:10.4230/lipics.stacs.2012.i · Cited by 171
Model checking probabilistic pushdown automata
Esparza, J., Kučera, A., & Mayr, R. (2004) · doi:10.1109/lics.2004.23 · Cited by 124
Derandomizing polynomial identity tests means proving circuit lower bounds
Kabanets, V., & Impagliazzo, R. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780595 · Cited by 113
Grenander, U. (1978) · Springer eBooks · Cited by 89
Relating probabilistic grammars and automata
Abney, S. P., McAllester, D., & Pereira, F. M. B. (1999) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.3115/1034678.1034759 · Cited by 81
On the Decidability of Temporal Properties of Probabilistic Pushdown Automata
Brázdil, T., Kučera, A., & Stražovský, O. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31856-9_12 · Cited by 73
A characterization of the class of functions computable in polynomial time on Random Access Machines
Bertoni, A., Mauri, G., & Sabadini, N. (1981) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800076.802470 · Cited by 35
Brázdil, T., Esparza, J., & Kučera, A. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.19 · Cited by 30
Cited by
Sequential Model-Based Optimization for General Algorithm Configuration
Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25566-3_40 · Cited by 2,469
Bernstein, D. J., & Lange, T. (2017) · Nature · doi:10.1038/nature23461 · Cited by 1,242
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
Micciancio, D., & Peikert, C. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_41 · Cited by 1,224
Better Key Sizes (and Attacks) for LWE-Based Encryption
Lindner, R., & Peikert, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19074-2_21 · Cited by 688
Pseudorandom Functions and Lattices
Banerjee, A., Peikert, C., & Rosen, A. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_42 · Cited by 459
Metadata
- Authors
- Etessami, K., & Yannakakis, M.
- Venue
- Journal of the ACM
- Published
- 2009-01
- Volume
- 56
- Issue
- 1
- Pages
- 1-66
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2005059149
- Cited by
- 512
- References
- 38
- FWCI
- 50.22
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.