On a complete set of operations for factorizing codes

Clelia De Felice

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 O of operations exists such that each factorizing code can be obtained by using the operations in O and starting with prefix or suffix codes. 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 = {a,b}, precisely a 3-code, which cannot be obtained by decomposition or substitution.

How to cite

top

De Felice, Clelia. "On a complete set of operations for factorizing codes." RAIRO - Theoretical Informatics and Applications 40.1 (2010): 29-52. <http://eudml.org/doc/92788>.

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

TY - JOUR
AU - De Felice, Clelia
TI - On a complete set of operations for factorizing codes
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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 O of operations exists such that each factorizing code can be obtained by using the operations in O and starting with prefix or suffix codes. 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 = {a,b}, 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/92788
ER -

References

top
  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.  
  2. M. Anselmo, A Non-Ambiguous Decomposition of Regular Languages and Factorizing Codes. Discrete Appl. Math.126 (2003) 129–165.  
  3. J. Berstel and D. Perrin, Theory of Codes. Academic Press, New York (1985).  
  4. J. Berstel and D. Perrin, Trends in the Theory of Codes. Bull. EATCS29 (1986) 84–95.  
  5. J. Berstel and C. Reutenauer, Rational Series and Their Languages. EATCS Monogr. Theoret. Comput. Sci.12 (1988).  
  6. J.M. Boë, Une famille remarquable de codes indécomposables, in Proc. Icalp 78. Lect. Notes Comput. Sci.62 (1978) 105–112.  
  7. J.M. Boë, Sur les codes factorisants, in Théorie des Codes, Actes de la 7e École de Printemps d'Informatique Théorique, edited by D. Perrin. LITP and ENSTA, Paris (1980) 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.  
  9. V. Bruyère and C. De Felice, Synchronization and decomposability for a family of codes: Part 2. Discrete Math.140 (1995) 47–77.  
  10. V. Bruyère and M. Latteux, Variable-Length Maximal Codes, in Proc. Icalp 96. Lect. Notes Comput. Sci.1099 (1996) 24–47.  
  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. Theory6 (1972) 221–225.  
  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.  
  14. C. De Felice, Construction of a family of finite maximal codes. Theoret. Comput. Sci.63 (1989) 157–184.  
  15. C. De Felice, A partial result about the factorization conjecture for finite variable-length codes. Discrete Math.122 (1993) 137–152.  
  16. C. De Felice, An application of Hajós factorizations to variable-length codes. Theoret. Comput. Sci.164 (1996) 223–252.  
  17. C. De Felice, Factorizing Codes and Schützenberger Conjectures, in Proc. MFCS 2000. Lect. Notes Comput. Sci.1893 (2000) 295–303.  
  18. C. De Felice, On some Schützenberger Conjectures. Inform. Comp.168 (2001) 144–155.  
  19. C. De Felice, An enhanced property of factorizing codes. Theor. Comput. Sci.340 (2005) 240–256.  
  20. C. De Felice and A. Restivo, Some results on finite maximal codes. RAIRO-Inform. Theor. Appl.19 (1985) 383–403.  
  21. C. De Felice and C. Reutenauer, Solution partielle de la conjecture de factorisation des codes. C.R. Acad. Sci. Paris302 (1986) 169–170.  
  22. D. Derencourt, A three-word code which is not prefix-suffix composed. Theor. Comput. Sci.163 (1996) 145–160.  
  23. L. Fuchs, Abelian groups. Pergamon Press, New York (1960).  
  24. G. Hajós, Sur la factorisation des groupes abéliens. Casopis Pest. Mat. Fys.74 (1950) 157–162.  
  25. M. Krasner and B. Ranulac, Sur une propriété des polynômes de la division du cercle. C.R. Acad. Sci. Paris240 (1937) 397–399.  
  26. N.H. Lam, A note on codes having no finite completions. Inform. Proc. Lett.55 (1995) 185–188.  
  27. N.H. Lam, Hajós factorizations and completion of codes. Theor. Comput. Sci.182 (1997) 245–256.  
  28. J. Neraud and C. Selmi, Locally complete sets and finite decomposable codes. Theor. Comput. Sci.273 (2002) 185–196.  
  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.  
  30. D. Perrin, Codes asynchrones. Bull. Soc. Math. France105 (1977) 385–404.  
  31. D. Perrin, Polynôme d'un code, in Théorie des Codes, Actes de la 7e École de Printemps d'Informatique Théorique, edited by D. Perrin. LITP and ENSTA, Paris (1980) 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.  
  33. A. Restivo, On codes having no finite completions. Discrete Math.17 (1977) 309–316.  
  34. A. Restivo, Codes and local constraints. Theor. Comput. Sci.72 (1990) 55–64.  
  35. A. Restivo, S. Salemi and T. Sportelli, Completing codes. RAIRO-Inf. Theor. Appl.23 (1989) 135–147.  
  36. A. Restivo and P.V. Silva, On the lattice of prefix codes. Theor. Comput. Sci.289 (2002) 755–782.  
  37. C. Reutenauer, Sulla fattorizzazione dei codici. Ricerche di Mat.XXXII (1983) 115–130.  
  38. C. Reutenauer, Non commutative factorization of variable-length codes. J. Pure Appl. Algebra36 (1985) 167–186.  
  39. A.D. Sands, On the factorisation of finite abelian groups. Acta Math. Acad. Sci. Hungaricae8 (1957) 65–86.  
  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. M. Vincent, Construction de codes indécomposables. RAIRO-Inf. Theor. Appl.19 (1985) 165–178.  
  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.  

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.