Some decompositions of Bernoulli sets and codes

Dipartimento di Matematica e Applicazioni dell'Università di Napoli “Federico II”, via Cintia, Complesso Universitario di Monte S. Angelo, 80126 Napoli, Italy and Istituto di Cibernetica “E. R. Caianiello” del CNR, 80078 Pozzuoli, Italy; aldo.deluca@dma.unina.it

Abstract

A decomposition of a set X of words over a d-letter alphabet A = {a₁,...,a_d} is any sequence X₁,...,X_d,Y₁,...,Y_d of subsets of A* such that the sets X_i, i = 1,...,d, are pairwise disjoint, their union is X, and for all i, 1 ≤ i ≤ d, X_i ~ a_iY_i, where ~ denotes the commutative equivalence relation. We introduce some suitable decompositions that we call good, admissible, and normal. A normal decomposition is admissible and an admissible decomposition is good. We prove that a set is commutatively prefix if and only if it has a normal decomposition. In particular, we consider decompositions of Bernoulli sets and codes. We prove that there exist Bernoulli sets which have no good decomposition. Moreover, we show that the classical conjecture of commutative equivalence of finite maximal codes to prefix ones is equivalent to the statement that any finite and maximal code has an admissible decomposition.