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), p. 29-52 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2006-01-01
DOI : https://doi.org/10.1051/ita:2005040
Classification:  94A45,  68Q45,  20K01 
@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},
     volume = {40},
     year = {2006},
     pages = {29-52},
     doi = {10.1051/ita:2005040},
     mrnumber = {2197282},
     zbl = {1091.94017},
     language = {en},
     url = {http://dml.mathdoc.fr/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, Tome 40 (2006) pp. 29-52. doi : 10.1051/ita:2005040. http://gdmltest.u-ga.fr/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