Geodesic
On a complete set of operations for factorizing codes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 29-52.

Voir la notice de l'article provenant de la source Numdam

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 : 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},
     pages = {29--52},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {1},
     year = {2006},
     doi = {10.1051/ita:2005040},
     mrnumber = {2197282},
     zbl = {1091.94017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005040/}
}
TY  - JOUR
AU  - Felice, Clelia De
TI  - On a complete set of operations for factorizing codes
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 29
EP  - 52
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005040/
DO  - 10.1051/ita:2005040
LA  - en
ID  - ITA_2006__40_1_29_0
ER  - 
%0 Journal Article
%A Felice, Clelia De
%T On a complete set of operations for factorizing codes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 29-52
%V 40
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005040/
%R 10.1051/ita:2005040
%G en
%F 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) no. 1, pp. 29-52. doi : 10.1051/ita:2005040. http://geodesic.mathdoc.fr/articles/10.1051/ita:2005040/

[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). | Zbl | MR

[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). | Zbl | MR

[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. | Zbl | mathdoc-id

[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). | Zbl | MR

[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. | Zbl | mathdoc-id

[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. | Zbl | mathdoc-id

[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. | mathdoc-id

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

[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

Cité par Sources :