A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars

DOI10.1016/j.ipl.2013.02.015zbMath1371.68202OpenAlexW2055776578MaRDI QIDQ396602

Stefan Kiefer, Javier Esparza, Andreas Gaiser

Publication date: 13 August 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.02.015

zbMATH Keywords

branching processesstochastic context-free grammarsstrongly polynomial algorithmexact matrix computations

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

Model-free reinforcement learning for branching Markov decision processes ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games

Uses Software

• QSopt_ex

Cites Work

• Computation of distances for regular and context-free probabilistic languages
• Geometric algorithms and combinatorial optimization.
• Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• Biological Sequence Analysis
• Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars