Construction of a family of finite maximal codes. (English) Zbl 0667.68079

The author introduces a family \({\mathcal F}\) of finite maximal codes over a two-letters alphabet \(A=\{a,b\}\), defined as the set of finite codes C verifying: \[ C-1=p(A-1)S\quad \Leftrightarrow \quad A^*=SC^*P \] where P,S are finite subsets of \(A^*\) such that either P or S is contained in \(a^*\). It is shown that every finite maximal code with two b’s is in \({\mathcal F}\). The main result of the paper consists on an algorithmical characterization of \({\mathcal F}\). Indeed, an algorithm based on the effective resolution of the inequality: \[ a^ M=\sum_{m\in M}(M,m)a^ m\leq a^{M+I+1}+a^ I \] where I is a given subset of \({\mathbb{N}}\) and M is a unknown subset of \({\mathbb{N}}\) is proposed in order to compute any code of \({\mathcal F}\). The paper ends with an application to the construction of all factorizations (T,R) of \({\mathbb{Z}}/n{\mathbb{Z}}\)- i.e., of subsets of \({\mathbb{N}}\) such that each element of \(\{\) 0,...,n-1\(\}\) can be written uniquely as a sum modulo n of an element of T and of an element of R - such that \(a^ T\) or \(a^ R\) is one factor of a polynomial factorization of \(P(n)=1+a+...+a^{n-1}\).
Reviewer: D.Krob


68Q45 Formal languages and automata
94A45 Prefix, length-variable, comma-free codes
Full Text: DOI


[1] Berstel, J.; Perrin, D., The theory of codes, (1985), Academic Press New York · Zbl 1022.94506
[2] Berstel, J.; Perrin, D., Trends in the theory of codes, Bull. EATCS no. 29, 85-95, (1986) · Zbl 1022.94506
[3] Berstel, J.; Reutenauer, C., Rational series and their languages, (), details yet? · Zbl 0522.68077
[4] Boë, J.M., Sur LES codes synchronisants coupants, (), Quaderni Della ricerca scientifica del CNR, 109, 7-10, (1981) · Zbl 0542.20046
[5] Boë, J.M., Sur LES codes factorisants, (), 1-8
[6] De Felice, C.; Restivo, A., Some results on finite maximal codes, RAIRO inform. théor., 19, 383-403, (1985) · Zbl 0578.68062
[7] De Felice, C.; Reutenauer, C., Solution partielle de la conjecture de factorisation des codes, C.R. acad. sci. Paris, 302, 169-170, (1986) · Zbl 0616.68066
[8] Eilenberg, S., Automata, languages and machines, Vol. A, (1974), Academic Press New York · Zbl 0317.94045
[9] Fuchs, L., Abelian groups, (1960), Pergamon Press Oxford · Zbl 0100.02803
[10] Krasner, M.; Ranulac, B., Sur une propriétédes polynoˆmes de la division du cercle, C.R. acad. sci. Paris, 240, 397-399, (1937) · JFM 63.0044.03
[11] Perrin, D.; Schützenberger, M.P., Un problémeélémentaire de la théorie de l’information, Colloques internationaux du CNRS no. 276, (1977), Cachan
[12] Restivo, A., On codes having no finite completion, Discrete math., 17, 309-316, (1977) · Zbl 0357.94011
[13] Restivo, A.; Salemi, S.; Sportelli, T., Completing codes, () · Zbl 0669.94012
[14] Reutenauer, C., Sulla fattorizzazione dei codici, Ricerche mat., XXXII, 115-130, (1983) · Zbl 0543.68063
[15] Reutenauer, C., Noncommutative factorization of variable-length codes, J.P. appl. algebra, 36, 167-186, (1985) · Zbl 0629.68079
[16] C. Reutenauer, Private communication, 1986.
[17] S. Salemi, Private communication, 1987.
[18] Schützenberger, M.P., Une théorie algébrique du codage, Séminaire dubreil-Pisot, (1955-1956), ExposéNo. 15
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.