Decoding for channels with insertions, deletions, and substitutions with applications to speech recognition

A model for channels in which an input sequence can produce output sequences of varying length is described. An efficient computational procedure for calculating Pr is devised, where and are the input and output of the channel. A stack decoding algorithm for decoding on such channels is presented. The appropriate likelihood function is derived. Channels with memory are considered. Some applications to speech and character recognition are discussed.