Note on decipherability of three-word codes. (22nd May 2002)

• Record Type: Journal Article
• Authors: Blanchet-Sadri, F.; Howell, T.
• Is Part Of: International journal of mathematics and mathematical sciences. Volume 30:Number 8(2002)
• Page Start: 491
• Page End: 504
• Publication Date: 2002-05-22
• Subjects: Mathematics -- Periodicals; 510.5
• DOI: 10.1155/S0161171202011729
• Languages: English
• ISSNs: 0161-1712

Abstract

Abstract : The theory of uniquely decipherable( UD ) codes has been widely developed in connection with automata theory, combinatorics on words, formal languages, and monoid theory. Recently, the concepts of multiset decipherable( MSD ) and set decipherable( SD ) codes were developed to handle some special problems in the transmission of information. Unique decipherability is a vital requirement in a wide range of coding applications where distinct sequences of code words carry different information. However, in several applications, it is necessary or desirable to communicate a description of a sequence of events where the information of interest is the set of possible events, including multiplicity, but where the order of occurrences is irrelevant. Suitable codes for these communication purposes need not possess theUD property, but the weakerMSD property. In other applications, the information of interest may be the presence or absence of possible events. TheSD property is adequate for such codes. Lempel (1986) showed that theUD andMSD properties coincide for two-word codes and conjectured that every three-wordMSD code is aUD code. Guzmán (1995) showed that theUD, MSD, andSD properties coincide for two-word codes and conjectured that these properties coincide for three-word codes. In an earlier paper (2001), Blanchet-Sadri answered both conjectures positively for all three-word codes{ c 1, c 2, c 3 } satisfying| c 1 | = | c 2 | ≤ | c 3 | . In this note, we answer both conjectures positively for other special three-word codes. Our procedures are based on techniques related to dominoes.