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:qucosa:25992 |
| Date | 10 May 2012 |
| Creators | Stüber, Torsten |
| Publisher | Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:workingPaper, info:eu-repo/semantics/workingPaper, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | urn:nbn:de:bsz:14-qucosa-79344, qucosa:24841 |
Page generated in 0.002 seconds