A decision procedure for the unique decipherability of multivalued encodings (Corresp.)

It is shown that there exists an algorithm to determine whether or not a given multivalued variable-length encoding, that is, a variable-length code system in which more than one codeword may correspond to one source symbol, is uniquely decipherable. The proof is given in two steps. The problem is first reduced to a simpler one, that of determining the inclusion relation between two rather simple languages, a regular set and a language defined by two shortening homomorphisms. Then a concrete decision procedure is given for this simpler problem. Several further observations are made, including a conjectured decision method for the finite-delay property.