The Viterbi algorithm for subsets of stochastic context-free languages

The time complexity of finding the most probable derivation for stochastic context-free grammars is cubic in the size of the input. The Viterbi algorithm solves the same task in linear time for stochastic regular languages. We present two modified versions of this algorithm. One finds the most probable path and builds a parse tree for stochastic one-counter languages in quadratic time of the size of the input. The other finds the most probable derivation for stochastic linear languages, also in quadratic time.