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

Javier Esparza; Andreas Gaiser; Stefan Kiefer

doi:10.1016/j.ipl.2013.02.015

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

Javier Esparza
, Andreas Gaiser
, Stefan Kiefer

Informatics 7 - Chair of Theoretical Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

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.

Original language	English
Pages (from-to)	381-385
Number of pages	5
Journal	Information Processing Letters
Volume	113
Issue number	10-11
DOIs	https://doi.org/10.1016/j.ipl.2013.02.015
State	Published - 2013

Keywords

Algorithms Branching processes Stochastic context-free grammars Exact matrix computations

Access to Document

10.1016/j.ipl.2013.02.015

Cite this

@article{bf3bcc6d99ba46538bb48fe1f7e04385,

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

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",

author = "Javier Esparza and Andreas Gaiser and Stefan Kiefer",

note = "Funding Information: ✩ Some results of this note are contained in the same authors{\textquoteright} 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.",

year = "2013",

doi = "10.1016/j.ipl.2013.02.015",

language = "English",

volume = "113",

pages = "381--385",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "10-11",

}

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 - https://www.scopus.com/pages/publications/84875753628

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 -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this