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

DOI10.1145/1462153.1462154zbMath1325.68091OpenAlexW2005059149MaRDI QIDQ3452195

Kousha Etessami, Mihalis Yannakakis

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1462153.1462154

zbMATH Keywords

Newton's methodmulti-type branching processesstochastic context-free grammarsrecursive Markov chainsmonotone nonlinear systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of solutions to systems of equations (65H10) Numerical analysis or methods applied to Markov chains (65C40) Grammars and rewriting systems (68Q42) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Optimal probabilistic generation of XML documents ⋮ Hyperplane separation technique for multidimensional mean-payoff games ⋮ Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations ⋮ Model-free reinforcement learning for branching Markov decision processes ⋮ The Odds of Staying on Budget ⋮ Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes ⋮ Stochastic Process Creation ⋮ Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy ⋮ Ratio and Weight Quantiles ⋮ On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS ⋮ Branching-time model-checking of probabilistic pushdown automata ⋮ A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars ⋮ Be lazy and don't care: faster CTL model checking for recursive state machines ⋮ Recursive stochastic games with positive rewards ⋮ Model Checking Temporal Properties of Recursive Probabilistic Programs ⋮ Convergence of Newton's method over commutative semirings ⋮ Space-efficient scheduling of stochastically generated tasks ⋮ Good edit similarity learning by loss minimization ⋮ A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes ⋮ Markov chains and Markov decision processes in Isabelle/HOL ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Equilibria, fixed points, and complexity classes ⋮ Unnamed Item ⋮ On Probabilistic Parallel Programs with Process Creation and Synchronisation ⋮ Runtime Analysis of Probabilistic Programs with Unbounded Recursion ⋮ Model checking with probabilistic tabled logic programming ⋮ Analyzing probabilistic pushdown automata ⋮ Language equivalence of probabilistic pushdown automata ⋮ Derivation tree analysis for accelerated fixed-point computation ⋮ Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the metric-based approximate minimization of Markov chains ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games ⋮ Runtime analysis of probabilistic programs with unbounded recursion ⋮ Unnamed Item ⋮ Equational theories for automata