01254094

a

01254094 De Felice, Clelia Completing codes by Haj\'os factorizations of groups. Almeida, Jorge (ed.) et al., Semigroups, automata and languages. Papers from the conference, Porto, Portugal, June 20-24, 1994. Singapore: World Scientific. 59-66 (1996). 1996 Singapore: World Scientific EN variable-length code embedding problem factorizations of cyclic groups finite maximal codes factorization conjecture Haj\'os factorizations Zbl 0669.94012 From the introduction: A variable-length code is the base of a free submonoid of $A^*$, that is a set of words $C$, over an alphabet $A$, such that any message written by using the words in $C$ as code words can be uniquely decoded. The algebraic theory of codes was initiated by Sch\"utzenberger. An important property of a code is maximality, a maximal code being a code that is not properly included in any other code over the same alphabet. An intriguing problem in the theory of variable-length codes is to characterize those finite codes that can be embedded in a finite maximal one. Actually, it is not even known whether this property is effectively decidable. This problem is a particular case of a more general one: given a code $C$ having property $P$, does there exist a maximal code $C'$ containing $C$ and retaining the property $P$? Despite its difficulty, there are nice partial results for this problem, namely for recognizable codes, for prefix and suffix codes, for codes with bounded deciphering delay, and for biprefix codes. Another recent direction of research consists in translating the embedding problem in terms of some properties of automata. In this paper, we concentrate on the embedding problem for finite codes and restrict ourselves to a two-letter alphabet $A= \{a,b\}$. Some partial results about this problem are known. However, the general structure of the factorizations of cyclic groups is still unknown, and some conjectures on it have been made. In this paper, we partially answer an open question of [{\it A. Restivo}, {\it S. Salemi} and {\it T. Sportelli}, Completing codes, RAIRO, Inf. Th\'eor. Appl. 23, 135-147 (1989; Zbl 0669.94012)]. We give a new characterization of a family of factorizations discovered by Haj\'os. The new characterization shows interesting relationships between factorizations and some finite maximal codes. We link the embedding problem to the factorization conjecture, proposed by Sch\"utzenberger, via Haj\'os factorizations. Finally, we prove that the embedding problem for a particular class of codes is decidable.