On a complete set of operations for factorizing codes

Clelia De Felice

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2006)

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

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 = { a , b } , 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 – ( 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. 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.