Note on decipherability of three-word codes
type: Item
instance of: scholarly article
title: Note on decipherability of three-word codes
zbMATH Open document ID: 1004.94014
DOI: 10.1155/S0161171202011729
author: R. Smith
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2002-08-12T00:00:00Z
full work available at URL: https://eudml.org/doc/49741
full work available at URL: S0161171202011729.html
review text: Summary: The theory of uniquely decipherable \((\text{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 \((\text{MSD})\) and set decipherable \((\text{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 \(\text{UD}\) property, but the weaker \(\text{MSD}\) property. In other applications, the information of interest may be the presence or absence of possible events. The \(\text{SD}\) property is adequate for such codes. \textit{A. Lempel} [IEEE Trans. Inf. Theory 32, 714-716 (1986; Zbl 0619.94019)] showed that the \(\text{UD}\) and \(\text{MSD}\) properties coincide for two-word codes and conjectured that every three-word \(\text{MSD}\) code is a \(\text{UD}\) code. \textit{F. Guzmán} (1995) showed that the \(\text{UD}\), \(\text{MSD}\), and \(\text{SD}\) properties coincide for two-word codes and conjectured that these properties coincide for three-word codes. In an earlier paper [IEEE Trans. Inf. Theory 47, 1745-1751 (2001)], \textit{F. Blanchet-Sadri} answered both conjectures positively for all three-word codes \(\{c_{1},c_{2},c_{3}\}\) satisfying \(|c_{1}|= |c_{2}|\leq |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.
Mathematics Subject Classification ID: 94A45
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 94B35
Mathematics Subject Classification ID: 05A99
zbMATH DE Number: 1779131
zbMATH Keywords: uniquely decipherable codes
zbMATH Keywords: multiset decipherable codes
zbMATH Keywords: set-decipherable codes
zbMATH Keywords: domino techniques
MaRDI profile type: Publication
OpenAlex ID: W2075788126
description: scientific article; zbMATH DE number 1779131