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

de Felice, Clelia

Theor. Comput. Sci. 63, No. 2, 157-184 (1989).

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

MSC:

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

Keywords:

factorizing code; factorization of Z/nZ; finite maximal codes; polynomial factorization

References:

[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