On a complete set of operations for factorizing codes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 40 (2006) no. 1, p. 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.

DOI : https://doi.org/10.1051/ita:2005040
Classification:  94A45,  68Q45,  20K01
Keywords: variable length codes, formal languages, factorizations of cyclic groups
@article{ITA_2006__40_1_29_0,
     author = {Felice, Clelia De},
     title = {On a complete set of operations for factorizing codes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {1},
     year = {2006},
     pages = {29-52},
     doi = {10.1051/ita:2005040},
     zbl = {1091.94017},
     mrnumber = {2197282},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2006__40_1_29_0}
}
Felice, Clelia De. On a complete set of operations for factorizing codes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 40 (2006) no. 1, pp. 29-52. doi : 10.1051/ita:2005040. http://www.numdam.org/item/ITA_2006__40_1_29_0/

[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 0996.68089

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

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

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

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

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

[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 0763.94004

[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 0842.94009

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

[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 0241.94015

[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 0338.94004

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

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

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

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

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

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

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

[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 0616.68066

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

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

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

[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 63.0044.03

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

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

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

[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 0208.45101

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

[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 0483.94028

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

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

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

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

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

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

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

[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 0567.68046

[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 0873.94011