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 \Y X\ is devised, where X = x₁, x₂, , xM and Y = y₁, y₂, , yN 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.