Complexity of acceptors for prefix codes (Corresp.)

For a given finite set of messages and their assigned probabilities, Huffman\´s procedure gives a method of computing a length set (a set of codeword lengths) that is optimal in the sense that the average word length is minimized. Corresponding to a particular length set, however, there may be more than one code. Let consist of all length sets with largest term , and, for any , let be the smallest number of states in any finite-state acceptor which accepts a set of codewords with length set . It is shown that, for all ,