FINITE COMPLETIONS VIA FACTORIZING CODES

摘要

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 Schutzenberger'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 C1 = C ∩ a*ba* satisfies a structural property defined by means of the Hajos 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 Hajos factorizations and starting with a special equation associated with C1 = 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 C1 = C ∩ a*ba* and as a consequence C1 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 C_1=C∩a*ba* ∈F. We also give a method of finding solutions to the above-mentioned equation associated with C1 and we conjecture that this method constructs all these solutions.