Unique Decipherability for Partially Commutative Alphabets

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.