Coding Partitions
Fabio Burderi, Antonio Restivo
Abstract
Motivated by the study of decipherability conditions for codes
weaker than Unique Decipherability (UD), we introduce the notion
of coding partition. Such a notion generalizes that of UD
code and, for codes that are not UD, allows to recover the
``unique decipherability" at the level of the classes of the
partition. By tacking into account the natural order between the
partitions, we define the characteristic partition of a code
X as the finest coding partition of X. This leads to introduce
the canonical decomposition of a code in at most one
unambiguous component and other (if any) totally ambiguous
components. In the case the code is finite, we give an algorithm
for computing its canonical partition. This, in particular, allows
to decide whether a given partition of a finite code X is a
coding partition. This last problem is then approached in the case
the code is a rational set. We prove its decidability under the
hypothesis that the partition contains a finite number of classes
and each class is a rational set. Moreover we conjecture that the
canonical partition satisfies such a hypothesis. Finally we
consider also some relationships between coding partitions and
varieties of codes.
Full Text: PostScript PDF