Some decompositions of Bernoulli sets and codes

Luca, Aldo de

doi:10.1051/ita:2005010

Luca, Aldo de

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 161-174.

Résumé

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 \leq i \leq d$ , $X_{i} \sim a_{i} Y_{i}$ , where $\sim$ 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.

MR Zbl

DOI : 10.1051/ita:2005010

Classification : 94A45
Mots clés : Bernoulli sets, codes, decompositions, commutative equivalence

@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},
     pages = {161--174},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     year = {2005},
     doi = {10.1051/ita:2005010},
     mrnumber = {2132585},
     zbl = {1073.94008},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2005010/}
}

TY  - JOUR
AU  - Luca, Aldo de
TI  - Some decompositions of Bernoulli sets and codes
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2005
SP  - 161
EP  - 174
VL  - 39
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2005010/
DO  - 10.1051/ita:2005010
LA  - en
ID  - ITA_2005__39_1_161_0
ER  -

%0 Journal Article
%A Luca, Aldo de
%T Some decompositions of Bernoulli sets and codes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 161-174
%V 39
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2005010/
%R 10.1051/ita:2005010
%G en
%F 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) no. 1, pp. 161-174. doi : 10.1051/ita:2005010. http://archive.numdam.org/articles/10.1051/ita:2005010/

Bibliographie
Cité par

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

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

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

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

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

[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

[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

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

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

Cité par Sources :