Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars

DOI10.1145/2213977.2214030zbMath1286.68188arXiv1201.2374OpenAlexW2142972886MaRDI QIDQ5415502

Alistair Stewart, Mihalis Yannakakis, Kousha Etessami

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.2374

zbMATH Keywords

polynomial time algorithmsprobabilistic systems of polynomial equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations ⋮ Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes ⋮ A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing ⋮ A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars ⋮ A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes ⋮ Unnamed Item ⋮ Analyzing probabilistic pushdown automata ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games ⋮ Approximate minimization of weighted tree automata

This page was built for publication: Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars