A Fast Algorithm for Computing Prefix Probabilities

Franz Nowak, Ryan Cotterell

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…