Reference:

Javier Esparza, Andreas Gaiser, and Stefan Kiefer. A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars. Information Processing Letters (IPL), 113(10–11):381–385, 2013.

Abstract:

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.

Suggested BibTeX entry:

@article{13EGK-IPL,
    author = {Javier Esparza and Andreas Gaiser and Stefan Kiefer},
    journal = {Information Processing Letters (IPL)},
    number = {10--11},
    pages = {381--385},
    title = {A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars},
    volume = {113},
    year = {2013}
}