# On a complete set of operations for factorizing codes

• Volume: 40, Issue: 1, page 29-52
• ISSN: 0988-3754

top

## Abstract

top
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=\left\{a,b\right\}$, precisely a $3-$code, which cannot be obtained by decomposition or substitution.

## How to cite

top

Felice, Clelia De. "On a complete set of operations for factorizing codes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 40.1 (2006): 29-52. <http://eudml.org/doc/245420>.

@article{Felice2006,
abstract = {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 $\{\mathcal \{O\}\}$ of operations exists such that each factorizing code can be obtained by using the operations in $\{\mathcal \{O\}\}$ and starting with prefix or suffix codes. $\{\mathcal \{O\}\}$ 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 = \lbrace a,b\rbrace$, precisely a $3-$code, which cannot be obtained by decomposition or substitution.},
author = {Felice, Clelia De},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {variable length codes; formal languages; factorizations of cyclic groups; free monoid generated by a finite alphabet},
language = {eng},
number = {1},
pages = {29-52},
publisher = {EDP-Sciences},
title = {On a complete set of operations for factorizing codes},
url = {http://eudml.org/doc/245420},
volume = {40},
year = {2006},
}

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
PB - EDP-Sciences
VL - 40
IS - 1
SP - 29
EP - 52
AB - 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 ${\mathcal {O}}$ of operations exists such that each factorizing code can be obtained by using the operations in ${\mathcal {O}}$ and starting with prefix or suffix codes. ${\mathcal {O}}$ 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 = \lbrace a,b\rbrace$, precisely a $3-$code, which cannot be obtained by decomposition or substitution.
LA - eng
KW - variable length codes; formal languages; factorizations of cyclic groups; free monoid generated by a finite alphabet
UR - http://eudml.org/doc/245420
ER -

## References

top
1. [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. Zbl0996.68089
2. [2] M. Anselmo, A Non-Ambiguous Decomposition of Regular Languages and Factorizing Codes. Discrete Appl. Math. 126 (2003) 129–165. Zbl1012.68100
3. [3] J. Berstel and D. Perrin, Theory of Codes. Academic Press, New York (1985). Zbl0587.68066MR797069
4. [4] J. Berstel and D. Perrin, Trends in the Theory of Codes. Bull. EATCS 29 (1986) 84–95. Zbl1022.94506
5. [5] J. Berstel and C. Reutenauer, Rational Series and Their Languages. EATCS Monogr. Theoret. Comput. Sci. 12 (1988). Zbl0668.68005MR971022
6. [6] J.M. Boë, Une famille remarquable de codes indécomposables, in Proc. Icalp 78. Lect. Notes Comput. Sci. 62 (1978) 105–112. Zbl0402.94036
7. [7] J.M. Boë, Sur les codes factorisants, in Théorie des Codes, Actes de la 7${}^{e}$ École de Printemps d’Informatique Théorique, edited by D. Perrin. LITP and ENSTA, Paris (1980) 1–8.
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. Zbl0763.94004
9. [9] V. Bruyère and C. De Felice, Synchronization and decomposability for a family of codes: Part 2. Discrete Math. 140 (1995) 47–77. Zbl0842.94009
10. [10] V. Bruyère and M. Latteux, Variable-Length Maximal Codes, in Proc. Icalp 96. Lect. Notes Comput. Sci. 1099 (1996) 24–47. Zbl1046.94511
11. [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. [12] Y. Césari, Sur un algorithme donnant les codes bipréfixes finis. Math. Syst. Theory 6 (1972) 221–225. Zbl0241.94015
13. [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. Zbl0338.94004
14. [14] C. De Felice, Construction of a family of finite maximal codes. Theoret. Comput. Sci. 63 (1989) 157–184. Zbl0667.68079
15. [15] C. De Felice, A partial result about the factorization conjecture for finite variable-length codes. Discrete Math. 122 (1993) 137–152. Zbl0798.68084
16. [16] C. De Felice, An application of Hajós factorizations to variable-length codes. Theoret. Comput. Sci. 164 (1996) 223–252. Zbl0864.94014
17. [17] C. De Felice, Factorizing Codes and Schützenberger Conjectures, in Proc. MFCS 2000. Lect. Notes Comput. Sci. 1893 (2000) 295–303. Zbl0996.68087
18. [18] C. De Felice, On some Schützenberger Conjectures. Inform. Comp. 168 (2001) 144–155. Zbl1007.68097
19. [19] C. De Felice, An enhanced property of factorizing codes. Theor. Comput. Sci. 340 (2005) 240–256. Zbl1079.68031
20. [20] C. De Felice and A. Restivo, Some results on finite maximal codes. RAIRO-Inform. Theor. Appl. 19 (1985) 383–403. Zbl0578.68062
21. [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. Zbl0616.68066
22. [22] D. Derencourt, A three-word code which is not prefix-suffix composed. Theor. Comput. Sci. 163 (1996) 145–160. Zbl0874.68169
23. [23] L. Fuchs, Abelian groups. Pergamon Press, New York (1960). Zbl0100.02803MR111783
24. [24] G. Hajós, Sur la factorisation des groupes abéliens. Casopis Pest. Mat. Fys. 74 (1950) 157–162. Zbl0039.01901
25. [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. Zbl63.0044.03JFM63.0044.03
26. [26] N.H. Lam, A note on codes having no finite completions. Inform. Proc. Lett. 55 (1995) 185–188. Zbl1023.68572
27. [27] N.H. Lam, Hajós factorizations and completion of codes. Theor. Comput. Sci. 182 (1997) 245–256. Zbl1053.20531
28. [28] J. Neraud and C. Selmi, Locally complete sets and finite decomposable codes. Theor. Comput. Sci. 273 (2002) 185–196. Zbl0996.68055
29. [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. Zbl0208.45101
30. [30] D. Perrin, Codes asynchrones. Bull. Soc. Math. France 105 (1977) 385–404. Zbl0391.94017
31. [31] D. Perrin, Polynôme d’un code, in Théorie des Codes, Actes de la 7${}^{e}$ École de Printemps d’Informatique Théorique, edited by D. Perrin. LITP and ENSTA, Paris (1980) 169–176.
32. [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. Zbl0483.94028
33. [33] A. Restivo, On codes having no finite completions. Discrete Math. 17 (1977) 309–316. Zbl0357.94011
34. [34] A. Restivo, Codes and local constraints. Theor. Comput. Sci. 72 (1990) 55–64. Zbl0693.68047
35. [35] A. Restivo, S. Salemi and T. Sportelli, Completing codes. RAIRO-Inf. Theor. Appl. 23 (1989) 135–147. Zbl0669.94012
36. [36] A. Restivo and P.V. Silva, On the lattice of prefix codes. Theor. Comput. Sci. 289 (2002) 755–782. Zbl1061.94038
37. [37] C. Reutenauer, Sulla fattorizzazione dei codici. Ricerche di Mat. XXXII (1983) 115–130. Zbl0543.68063
38. [38] C. Reutenauer, Non commutative factorization of variable-length codes. J. Pure Appl. Algebra 36 (1985) 167–186. Zbl0629.68079
39. [39] A.D. Sands, On the factorisation of finite abelian groups. Acta Math. Acad. Sci. Hungaricae 8 (1957) 65–86. Zbl0079.03303
40. [40] M.P. Schützenberger, Une théorie algébrique du codage, Séminaire Dubreil-Pisot 1955–56, exposé No. 15 (1955), 24 p.
41. [41] M. Vincent, Construction de codes indécomposables. RAIRO-Inf. Theor. Appl. 19 (1985) 165–178. Zbl0567.68046
42. [42] L. Zhang and C.K. Gu, Two classes of factorizing codes – $\left(p,p\right)$-codes and $\left(4,4\right)$-codes, in Words, Languages and Combinatorics II, edited by M. Ito and H. Jürgensen. World Scientific (1994) 477–483. Zbl0873.94011

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.