Metadata only
Date
2023-07Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Multiple algorithms are known for efficiently calculating the prefix probability of a string under a probabilistic context-free grammar (PCFG). Good algorithms for the problem have a runtime cubic in the length of the input string. However, some proposed algorithms are suboptimal with respect to the size of the grammar. This paper proposes a novel speed-up of Jelinek and Lafferty's (1991) algorithm, which runs in O(N³|N|³ + |N|⁴), where N is the input length and |N | is the number of non-terminals in the grammar. In contrast, our speed-up runs in O(N²|N|³ + N³|N|²). Show more
Publication status
publishedExternal links
Book title
Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics, Volume 2: Short PapersPages / Article No.
Publisher
Association for Computational LinguisticsEvent
More
Show all metadata
ETH Bibliography
yes
Altmetrics