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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:14-qucosa-86943 |
| Date | 10 May 2012 |
| Creators | Stüber, Torsten |
| Contributors | Technische Universität Dresden, Fakultät Informatik |
| Publisher | Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:workingPaper |
| Format | application/pdf |
| Relation | dcterms:isPartOf:Technische Berichte / Technische Universität Dresden, Fakultät Informatik ; 2012,04 (TUD-FI12-04-März 2012) |
Page generated in 0.0018 seconds