Note on decipherability of three-word codes
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 proble...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2002-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/S0161171202011729 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850212527888138240 |
|---|---|
| author | F. Blanchet-Sadri T. Howell |
| author_facet | F. Blanchet-Sadri T. Howell |
| author_sort | F. Blanchet-Sadri |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-8a59875ec0224b88a6a28be14f6d20ed |
| institution | OA Journals |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2002-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-8a59875ec0224b88a6a28be14f6d20ed2025-08-20T02:09:18ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252002-01-0130849150410.1155/S0161171202011729Note on decipherability of three-word codesF. Blanchet-Sadri0T. Howell1Department of Mathematical Sciences, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402-6170, USADepartment of Mathematical Sciences, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402-6170, USAThe 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.http://dx.doi.org/10.1155/S0161171202011729 |
| spellingShingle | F. Blanchet-Sadri T. Howell Note on decipherability of three-word codes International Journal of Mathematics and Mathematical Sciences |
| title | Note on decipherability of three-word codes |
| title_full | Note on decipherability of three-word codes |
| title_fullStr | Note on decipherability of three-word codes |
| title_full_unstemmed | Note on decipherability of three-word codes |
| title_short | Note on decipherability of three-word codes |
| title_sort | note on decipherability of three word codes |
| url | http://dx.doi.org/10.1155/S0161171202011729 |
| work_keys_str_mv | AT fblanchetsadri noteondecipherabilityofthreewordcodes AT thowell noteondecipherabilityofthreewordcodes |