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

DOI10.1016/J.IPL.2013.02.015zbMATH Open1371.68202OpenAlexW2055776578MaRDI QIDQ396602FDOQ396602

Authors: Javier Esparza, Andreas Gaiser, Stefan Kiefer 

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

Recommendations

• Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars
• Consistency of stochastic context-free grammars
• Stochastic context-free grammars, regular languages, and newton's method
• A Polynomial Algorithm for the Inference of Context Free Languages
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Context-Free Grammars and Stable Multivariate Polynomials over Stirling Permutations
• A note on the expressive power of probabilistic context free grammars
• Random Context-Free Grammars: Supercritical Case with a Nonzero Extinction Probability

zbMATH Keywords

branching processesstochastic context-free grammarsstrongly polynomial algorithmexact matrix computations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Model-free reinforcement learning for branching Markov decision processes
• Recursive Markov decision processes and recursive stochastic games

Uses Software

• QSopt_ex

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396602)