Regular coding partitions

Regular coding partitions
y yMarie-Pierre Beal Fabio Burderi Antonio Restivo
June 11, 2006
Abstract
The canonical coding partition of a set of words is the nest partition such that the words contained
in at least two factorizations of a same sequence belong to a same class. In the case the set is not
uniquely decipherable, it partitions the set into one unambiguous class and other parts that localize
the ambiguities in the factorizations of nite sequences.
We prove that the canonical coding partition of a regular set contains a nite number of regular
classes. We give an algorithm for computing this partition.
1 Introduction
In this paper, we call code a set of nite words. An important class of codes is the class of uniquely
decipherable codes. This property allows the decoding of a sequence of concatenated codewords. Never-
theless, some classes of codes are used in information theory although they are not uniquely decipherable
(see for instance [6], [7] and [8]). The condition of unique decipherability can also be weakened by consid-
ering that it applies only to codes with constraints (see [1]) or to codes with a constraint source (see [4],
[5]). In [5], the classi cation of ambiguities of codes is investigated in the study of natural languages.
From a combinatorial point of view, the study of ambiguities helps to understand the structure of a code.
To this purpose, the notions of coding partition and canonical coding partition of a code were intro-
duced in [3] to ...