- title
- Consistency of Probabilistic Context-Free Grammars
- Please use the following URL when quoting:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-86943
- Series
- Technische Berichte
- multivolume_volume0
- 2012,04 (TUD-FI12-04-März 2012)
- Abstract (EN)
- 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.
- Keywords (DE)
- Kontextfreie Grammatik, Probabilistische Kontextfreie Grammatik, Konsistenz, Verarbeitung natürlicher Sprachen
- Keywords (EN)
- Context-free Grammar, Probabilistic Context-Free Grammar, Consistency, Natural Language Processing
- Classification (DDC)
- 004
- Classification (RVK)
- SS 5514
- university_publisher
- Technische Universität Dresden, Dresden
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa-86943
- Qucosa date of publication
- 10.05.2012
- Document type
- research_paper
- Document language
- English
- licence
