Computation of the probability of initial substring generation by stochastic context-free grammars

Speech recognition language models are based on probabilities P(Wk+I = v [ WlW2~..., Wk) that the next word Wk+l will be any particular word v of the vocabulary, given that the word sequence Wl, w2,..., Wk is hypothesized to have been uttered in the past. If probabilistic context-free grammars are to be used as the basis of the language model, it will be necessary to compute the probability that successive application of the grammar rewrite rules (beginning with the sentence start symbol s) produces a word string whose initial substring is an arbitrary sequence wl, w2,..., Wk+l. In this paper we describe a new algorithm that achieves the required computation in at most a constant times k3-steps. 1.