TY - JOUR
T1 - A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars
AU - Esparza, Javier
AU - Gaiser, Andreas
AU - Kiefer, Stefan
N1 - Funding Information:
✩ Some results of this note are contained in the same authors’ conference paper Computing least fixed points of probabilistic systems of polynomials, in: Proceedings of STACS, 2010, pp. 359–370. * Corresponding author. E-mail address: [email protected] (J. Esparza). 1 Supported by the DFG-Graduiertenkolleg 1480 (PUMA). 2 Supported by the EPSRC.
PY - 2013
Y1 - 2013
N2 - We provide a strongly polynomial algorithm for determining whether a given multi-type branching process is subcritical, critical, or supercritical. The same algorithm also decides consistency of stochastic context-free grammars.
AB - We provide a strongly polynomial algorithm for determining whether a given multi-type branching process is subcritical, critical, or supercritical. The same algorithm also decides consistency of stochastic context-free grammars.
KW - Algorithms Branching processes Stochastic context-free grammars Exact matrix computations
UR - http://www.scopus.com/inward/record.url?scp=84875753628&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2013.02.015
DO - 10.1016/j.ipl.2013.02.015
M3 - Article
AN - SCOPUS:84875753628
SN - 0020-0190
VL - 113
SP - 381
EP - 385
JO - Information Processing Letters
JF - Information Processing Letters
IS - 10-11
ER -