On unique, multiset, and set decipherability of three-word codes

The concepts of unique decipherability (UD), multiset decipherability (MSD), and set decipherability (SD) of codes were developed to handle some special problems in the transmission of information. In unique decipherability, different sequences of codewords carry different information. In multiset decipherability, the information of interest is the multiset of codewords used in the encoding process so that order in which transmitted words are received is immaterial. In set decipherability, it is the set of codewords that is relevant information so the order and the multiplicity of words are immaterial. Lempel (1986) showed that the UD and MSD properties coincide for two-word codes and conjectured that every three-word MSD code is a UD code. Guzman (1995) showed that the UD, MSD, and SD properties coincide for two-word codes and conjectured that these properties coincide for three-word codes. In this paper, we answer both conjectures positively for all three-word codes {C₁, C₂, C₃} satisfying |C₁|=|C₂|⩽|C₃ |. Our procedures are based on techniques related to dominoes