Several results relate finite maximal codes to factorizations of cyclic groups. In the case of
factorizing codes C, i.e. finite maximal codes which satisfy the still open Schützenberger's
factorization conjecture, special factorizations, discovered by Hajós, intervene. In particular, given a two-letter alphabet {a,b}, it is known that the set C
1 = C ∩ a
*ba
* satisfies a structural property defined by means of the Hajós factorizations. Conversely, it is not true that a set satisfying this structural property can be embedded in a factorizing code and some partial results are known on the problem of finding additional hypotheses that guarantee the existence of such embedding. Let C be a factorizing code. Inspired by the recursive construction of the Hajós factorizations and starting with a special equation associated with C
1 = C ∩ a
*ba
*, we define a family
of subsets of a
*ba
*, each of them still satisfying the above-mentioned structural property. We prove that for each set
, there exists a factorizing code C with C
1 = C ∩ a
*ba
* and as a consequence C
1 is a code. C is obtained starting with prefix/suffix codes and by using two types of operations on codes —
composition and
substitution. We extend all these results to alphabets of size greater than two. We conjecture that for each factorizing code C, we have
. We also give a method of finding solutions to the above-mentioned equation associated with C
1 and we conjecture that this method constructs
all these solutions.
