- AutorIn
- Dr. Torsten Stüber
- Titel
- Consistency of Probabilistic Context-Free Grammars
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-86943
- Schriftenreihe
- Technische Berichte
- Bandnummer
- 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.
- Freie Schlagwörter (DE)
- Kontextfreie Grammatik, Probabilistische Kontextfreie Grammatik, Konsistenz, Verarbeitung natürlicher Sprachen
- Freie Schlagwörter (EN)
- Context-free Grammar, Probabilistic Context-Free Grammar, Consistency, Natural Language Processing
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- SS 5514
- Publizierende Institution
- Technische Universität Dresden, Dresden
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa-86943
- Veröffentlichungsdatum Qucosa
- 10.05.2012
- Dokumenttyp
- Forschungsbericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis