Optimal Linguistic Decoding (OLD) is the task of finding a best description of an observed acoustic signal in terms of certain types of Linguistic Units such as phonemes, words, etc. So far, three main Dynamic Programming algorithms have been presented as alternative solutions to this decoding problem: Two Level, Level Building and One Stage (or Viterbi). It is generally accepted that all these algorithms solve the very same OLD problem and that they differ only in computational complexity aspects; however, this is not in fact the case. In this paper we show that different classes of increasingly difficult and interesting OLD problems can be identified and that not all the mentioned algorithms can actually solve all the problems. Level Building and One Stage can only solve a most restricted (least interesting) class. Two Level is significantly more powerful, properly accounting for a wide class of interesting OLD settings. Finally, no efficient algorithmic (exact) solution is known so far for the most traditional (and interesting) establishment of the OLD task. A formal characterization of these classes of problems is introduced in this paper, along with a discussion on their relative practical interest. Also, this characterization has allowed us to achieve a formal derivation of the above-mentioned classical algorithms along with some new, more efficient versions thereof.