Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-30T23:56:29.162Z Has data issue: false hasContentIssue false
  • English
  • Français

Some decompositions of Bernoulli sets and codes

Published online by Cambridge University Press:  15 March 2005

Aldo de Luca
Aldo de Luca*
Affiliation:
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; [email protected]
Get access

Abstract

A decomposition of a set X of words over a d-letter alphabet A = {a1,...,ad} is any sequence X1,...,Xd,Y1,...,Yd of subsets of A* such that the sets Xi, i = 1,...,d, are pairwise disjoint, their union is X, and for all i, 1 ≤ i ≤ d, Xi ~ aiYi, 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.

Keywords

Bernoulli setscodesdecompositionscommutative equivalence.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 1: Imre Simon, the tropical computer scientist , January 2005 , pp. 161 - 174
Copyright
© EDP Sciences, 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Berstel and D. Perrin, Theory of Codes. Academic Press, New York (1985).
A. Carpi and A. de Luca, Completions in measure of languages and related combinatorial problems. Theor. Comput. Sci. To appear.
de Felice, C., On the triangle conjecture. Inform. Process. Lett. 14 (1982) 197–200. CrossRef
de Luca, A., Some combinatorial results on Bernoulli sets and codes. Theor. Comput. Sci. 273 (2002) 143–165. CrossRef
Hansel, G., Baïonnettes et cardinaux. Discrete Math. 39 (1982) 331–335. CrossRef
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.
Perrin, D. and Schützenberger, M.P., A conjecture on sets of differences on integer pairs. J. Combin. Theory Ser. B 30 (1981) 91–93. CrossRef
Pin, J.E. and Simon, I., A note on the triangle conjecture. J. Comb. Theory Ser. A 32 (1982) 106–109. CrossRef
Shor, P., A counterexample to the triangle conjecture. J. Comb. Theory Ser. A 38 (1985) 110–112. CrossRef