Note on Decipherability of Three-Word Codes
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Francine Blanchet-Sadri, Professor (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
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 the UD property, but the weaker MSD property. In other applications,
the information of interest may be the presence or absence of possible events. The SD
property is adequate for such codes. 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. Guzmán (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 an earlier
paper (2001), Blanchet-Sadri answered both conjectures positively for all three-word codes
{c1,c2,c3} satisfying |c1| = |c2| = |c3|. In this note, we answer both conjectures positively
for other special three-word codes. Our procedures are based on techniques related to
dominoes.
Note on Decipherability of Three-Word Codes
PDF (Portable Document Format)
426 KB
Created on 2/21/2011
Views: 1929
Additional Information
- Publication
- International Journal of Mathematics and Mathematical Sciences 30(8), 491-504
- Language: English
- Date: 2002
- Keywords
- Decipherability, Words, Mathematical models, Monoids, Formal language