Return to search

Consistency of Probabilistic Context-Free Grammars

We present an algorithm for deciding whether an arbitrary proper probabilistic context-free grammar is consistent, i.e., whether the probability that a derivation terminates is one. Our procedure has time complexity $\\\\mathcal O(n^3)$ in the unit-cost model of computation. Moreover, we develop a novel characterization of consistent probabilistic context-free grammars. A simple corollary of our result is that training methods for probabilistic context-free grammars that are based on maximum-likelihood estimation always yield consistent grammars.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:14-qucosa-86943
Date10 May 2012
CreatorsStüber, Torsten
ContributorsTechnische Universität Dresden, Fakultät Informatik
PublisherSaechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:workingPaper
Formatapplication/pdf
Relationdcterms:isPartOf:Technische Berichte / Technische Universität Dresden, Fakultät Informatik ; 2012,04 (TUD-FI12-04-März 2012)

Page generated in 0.0018 seconds