Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars

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}
}

PDF (167 kB)
See dx.doi.org ...