|
|||||
|
|
A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars |
|
| Authors: | Javier Esparza Andreas Gaiser Stefan Kiefer |
| Affiliation: | 1. Technische Universität München, Germany;2. University of Oxford, UK |
| 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. |
| Keywords: | Algorithms Branching processes Stochastic context-free grammars Exact matrix computations |
| 本文献已被 ScienceDirect 等数据库收录！ | |