Multiset and set decipherable codes

DOI10.1016/S0898-1221(01)00096-7MaRDI QIDQ5948786zbMATH OpenOpenAlexFDO

Authors F. Blanchet-Sadri, C. Morgan

Publication date 12 November 2001

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0898-1221(01)00096-7

zbMATH Keywords

domino graphsmultiset decipherabilityprefix codesset decipherabilitysuffix codesunique decipherable codes

Mathematics Subject Classification ID

Paths and cycles (05C38) Prefix, length-variable, comma-free codes (94A45) Decoding (94B35)

Review text

Unique decipherable (UD) codes use different sequences of codewords to carry different information. In multiset decipherability (MSD), the order in which the codewords appears is irrelevant, whereas in set decipherability (SD), the order and multiplicity of words is irrelevant. Work of \textit{A. Lempel} [IEEE Trans. Inf. Theory 32, 714-716 (1986; Zbl 0619.94019)] and \textit{F. Guzmán} [A complete list of small proper MSD and SD codes (submitted)] shows that UD, MSD, and SD coincide for two-word codes. The first author has considered this question for three-word codes in [\textit{F. Blanchet-Sadri}, IEEE Trans. Inf. Theory 47, 1745-1757 (2001)], where he shows that UD, MSD, and SD coincide under certain conditions. Here, the authors show that UD, MSD, and SD cannot coincide for \(n\geq 4\) by providing a construction for an \(n\)-word SD code that is not MSD. Furthermore, they show that no SD code contains a full UD code as a proper subcode.

Recommendations

• On unique, multiset, and set decipherability of three-word codes
• Multiset, Set and Numerically Decipherable Codes over Directed Figures
• On multiset decipherable codes (Corresp.)
• Note on decipherability of three-word codes
• Decidability of multiset, set and numerically decipherable directed figure codes

Cites work

• A note on multiset decipherable codes
• Deciding multiset decipherability
• Decipherability of codes
• scientific article; zbMATH DE number 3883641 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 3316587 (Why is no real title available?)
• Note on decipherability of three-word codes
• On multiset decipherable codes (Corresp.)
• On unique, multiset, and set decipherability of three-word codes

Cited in

(10)

• Small sets of even type and codewords
• Note on decipherability of three-word codes
• Fuzzy multiset finite automata and their languages
• Unique decipherability in formal languages
• Multiset, Set and Numerically Decipherable Codes over Directed Figures
• On fuzzy multiset automata
• Factorization in formal languages
• On multiset decipherable codes (Corresp.)
• On unique, multiset, and set decipherability of three-word codes
• Deciding multiset decipherability

This page was built for publication: Multiset and set decipherable codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5948786)