Some decompositions of Bernoulli sets and codes
Luca, Aldo de
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005), p. 161-174 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

A decomposition of a set X of words over a d-letter alphabet A={a 1 ,...,a d } is any sequence X 1 ,...,X d ,Y 1 ,...,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 i Y 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.

Publié le : 2005-01-01
DOI : https://doi.org/10.1051/ita:2005010
Classification:  94A45 
@article{ITA_2005__39_1_161_0,
     author = {Luca, Aldo de},
     title = {Some decompositions of Bernoulli sets and codes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {39},
     year = {2005},
     pages = {161-174},
     doi = {10.1051/ita:2005010},
     mrnumber = {2132585},
     zbl = {1073.94008},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2005__39_1_161_0}
}

Luca, Aldo de. Some decompositions of Bernoulli sets and codes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) pp. 161-174. doi : 10.1051/ita:2005010. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_161_0/

[1] J. Berstel and D. Perrin, Theory of Codes. Academic Press, New York (1985). | MR 797069 | Zbl 0587.68066

[2] A. Carpi and A. De Luca, Completions in measure of languages and related combinatorial problems. Theor. Comput. Sci. To appear. | MR 2112765 | Zbl 1078.68077

[3] C. De Felice, On the triangle conjecture. Inform. Process. Lett. 14 (1982) 197-200. | Zbl 0487.68074

[4] A. De Luca, Some combinatorial results on Bernoulli sets and codes. Theor. Comput. Sci. 273 (2002) 143-165. | Zbl 0996.68146

[5] G. Hansel, Baïonnettes et cardinaux. Discrete Math. 39 (1982) 331-335. | Zbl 0486.20032

[6] D. Perrin and M.P. Schützenberger, Un problème élémentaire de la théorie de l'Information, in Theorie de l'Information, Colloq. Internat. du CNRS No. 276, Cachan (1977) 249-260. | Zbl 0483.94028

[7] D. Perrin and M.P. Schützenberger, A conjecture on sets of differences on integer pairs. J. Combin. Theory Ser. B 30 (1981) 91-93. | Zbl 0468.05033

[8] J.E. Pin and I. Simon, A note on the triangle conjecture. J. Comb. Theory Ser. A 32 (1982) 106-109. | Zbl 0472.05010

[9] P. Shor, A counterexample to the triangle conjecture. J. Comb. Theory Ser. A 38 (1985) 110-112. | Zbl 0558.20032