Publications

Advanced search

Abstract

Joan-Andreu Sánchez, José-Miguel Benedí. Computation of the probability of the best derivation of an initial substring from a stochastic context-free grammar. VII Spanish Symposium on Pattern Recognition and Image Analysis, 1997. Alberto Sanfeliu, Juan J. Villanueva, Jordi Vitrià (Editors). pp. 181-186. AERFAI.

Recently, Stochastic Context-Free Grammars have been considered important for use in Language Modeling for Automatic Speech Recognition tasks [Jelinek and Lafferty, 1991 and Ney, 1991]. In [Jelinek and Lafferty, 1991], Jelinek and Lafferty presented and solved the problem of computation of the probability of initial substring generation by using Stochastic Context-Free Grammars. This paper seeks to apply a Viterbi scheme to achieve the computation of the probability of the best derivation of an initial substring generated by a Stochastic Context-Free Grammar. The description of the algorithm that solves this computation, along with the study of its time complexity are also presented.