On a complete set of operations for factorizing codes

Felice, Clelia De

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 29-52.

It is known that the class of factorizing codes, i.e., codes satisfying the factorization conjecture formulated by Schützenberger, is closed under two operations: the classical composition of codes and substitution of codes. A natural question which arises is whether a finite set $𝒪$ of operations exists such that each factorizing code can be obtained by using the operations in $𝒪$ and starting with prefix or suffix codes. $𝒪$ is named here a complete set of operations (for factorizing codes). We show that composition and substitution are not enough in order to obtain a complete set. Indeed, we exhibit a factorizing code over a two-letter alphabet $A=\{a,b\}$, precisely a $3-$code, which cannot be obtained by decomposition or substitution.

[1] M. Anselmo, A Non-Ambiguous Decomposition of Regular Languages and Factorizing Codes, in Proc. DLT'99, G. Rozenberg, W. Thomas Eds. World Scientific (2000) 141-152. | Zbl

[2] M. Anselmo, A Non-Ambiguous Decomposition of Regular Languages and Factorizing Codes. Discrete Appl. Math. 126 (2003) 129-165. | Zbl

[3] J. Berstel and D. Perrin, Theory of Codes. Academic Press, New York (1985). | MR | Zbl

[4] J. Berstel and D. Perrin, Trends in the Theory of Codes. Bull. EATCS 29 (1986) 84-95. | Zbl

[5] J. Berstel and C. Reutenauer, Rational Series and Their Languages. EATCS Monogr. Theoret. Comput. Sci. 12 (1988). | MR | Zbl

[6] J.M. Boë, Une famille remarquable de codes indécomposables, in Proc. Icalp 78. Lect. Notes Comput. Sci. 62 (1978) 105-112. | Zbl

[7] J.M. Boë, Sur les codes factorisants1980) 1-8.

[8] V. Bruyère and C. De Felice, Synchronization and decomposability for a family of codes. Intern. J. Algebra Comput. 4 (1992) 367-393. | Zbl

[9] V. Bruyère and C. De Felice, Synchronization and decomposability for a family of codes: Part 2. Discrete Math. 140 (1995) 47-77. | Zbl

[10] V. Bruyère and M. Latteux, Variable-Length Maximal Codes, in Proc. Icalp 96. Lect. Notes Comput. Sci. 1099 (1996) 24-47. | Zbl

[11] M.G. Castelli, D. Guaiana and S. Mantaci, Indecomposable prefix codes and prime trees, in Proc. DLT 97 edited by S. Bozapadilis-Aristotel (1997).

[12] Y. Césari, Sur un algorithme donnant les codes bipréfixes finis. Math. Syst. Theory 6 (1972) 221-225. | Zbl

[13] Y. Césari, Sur l'application du théorème de Suschkevitch à l'étude des codes rationnels complets, in Proc. Icalp 74. Lect. Notes Comput. Sci. (1974) 342-350. | Zbl

[14] C. De Felice, Construction of a family of finite maximal codes. Theoret. Comput. Sci. 63 (1989) 157-184. | Zbl

[15] C. De Felice, A partial result about the factorization conjecture for finite variable-length codes. Discrete Math. 122 (1993) 137-152. | Zbl

[16] C. De Felice, An application of Hajós factorizations to variable-length codes. Theoret. Comput. Sci. 164 (1996) 223-252. | Zbl

[17] C. De Felice, Factorizing Codes and Schützenberger Conjectures, in Proc. MFCS 2000. Lect. Notes Comput. Sci. 1893 (2000) 295-303. | Zbl

[18] C. De Felice, On some Schützenberger Conjectures. Inform. Comp. 168 (2001) 144-155. | Zbl

[19] C. De Felice, An enhanced property of factorizing codes. Theor. Comput. Sci. 340 (2005) 240-256. | Zbl

[20] C. De Felice and A. Restivo, Some results on finite maximal codes. RAIRO-Inform. Theor. Appl. 19 (1985) 383-403. | Numdam | Zbl

[21] C. De Felice and C. Reutenauer, Solution partielle de la conjecture de factorisation des codes. C.R. Acad. Sci. Paris 302 (1986) 169-170. | Zbl

[22] D. Derencourt, A three-word code which is not prefix-suffix composed. Theor. Comput. Sci. 163 (1996) 145-160. | Zbl

[23] L. Fuchs, Abelian groups. Pergamon Press, New York (1960). | MR | Zbl

[24] G. Hajós, Sur la factorisation des groupes abéliens. Casopis Pest. Mat. Fys. 74 (1950) 157-162. | Zbl

[25] M. Krasner and B. Ranulac, Sur une propriété des polynômes de la division du cercle. C.R. Acad. Sci. Paris 240 (1937) 397-399. | JFM

[26] N.H. Lam, A note on codes having no finite completions. Inform. Proc. Lett. 55 (1995) 185-188. | Zbl

[27] N.H. Lam, Hajós factorizations and completion of codes. Theor. Comput. Sci. 182 (1997) 245-256. | Zbl

[28] J. Neraud and C. Selmi, Locally complete sets and finite decomposable codes. Theor. Comput. Sci. 273 (2002) 185-196. | Zbl

[29] M. Nivat, Éléments de la théorie générale des codes, in Automata Theory, edited by E. Caianiello. Academic Press, New York (1966) 278-294. | Zbl

[30] D. Perrin, Codes asynchrones. Bull. Soc. Math. France 105 (1977) 385-404. | Numdam | Zbl

[31] D. Perrin, Polynôme d'un code1980) 169-176.

[32] D. Perrin and M.P. Schützenberger, Un problème élémentaire de la théorie de l'information, Théorie de l'Information, Colloques Internat. CNRS, Cachan 276 (1977) 249-260. | Zbl

[33] A. Restivo, On codes having no finite completions. Discrete Math. 17 (1977) 309-316. | Zbl

[34] A. Restivo, Codes and local constraints. Theor. Comput. Sci. 72 (1990) 55-64. | Zbl

[35] A. Restivo, S. Salemi and T. Sportelli, Completing codes. RAIRO-Inf. Theor. Appl. 23 (1989) 135-147. | Numdam | Zbl

[36] A. Restivo and P.V. Silva, On the lattice of prefix codes. Theor. Comput. Sci. 289 (2002) 755-782. | Zbl

[37] C. Reutenauer, Sulla fattorizzazione dei codici. Ricerche di Mat. XXXII (1983) 115-130. | Zbl

[38] C. Reutenauer, Non commutative factorization of variable-length codes. J. Pure Appl. Algebra 36 (1985) 167-186. | Zbl

[39] A.D. Sands, On the factorisation of finite abelian groups. Acta Math. Acad. Sci. Hungaricae 8 (1957) 65-86. | Zbl

[40] M.P. Schützenberger, Une théorie algébrique du codage, Séminaire Dubreil-Pisot 1955-56, exposé No. 15 (1955), 24 p. | Numdam

[41] M. Vincent, Construction de codes indécomposables. RAIRO-Inf. Theor. Appl. 19 (1985) 165-178. | Numdam | Zbl

[42] L. Zhang and C.K. Gu, Two classes of factorizing codes - $(p,p)$-codes and $(4,4)$-codes, in Words, Languages and Combinatorics II, edited by M. Ito and H. Jürgensen. World Scientific (1994) 477-483. | Zbl