Unique Decipherability for Partially Commutative Alphabets

Article type: Research Article

Authors: Chrobak, Marek | Rytter, Wojciech^{; *}

Affiliations: Institute of Informatics, Warsaw University, PKiN VIII p, 00-901 Warsaw, Poland

Note: [*] This work was made partially when the second author was visiting University of Salerno, Dept. of Informatics.

Abstract: We consider the unique decipherability problem for partially commutative alphabets. It is shown that the decidability of the problem depends heavily on the size of the alphabet and the structure of the graph of the commutativity relation. In particular, for alphabets with at most three letters the problem is decidable and for alphabets of bigger size the problem is undecidable.

DOI: 10.3233/FI-1987-10305

Journal: Fundamenta Informaticae, vol. 10, no. 3, pp. 323-336, 1987