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 , precisely a code, which cannot be obtained by decomposition or substitution.
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/articles/10.1051/ita:2005040/
[1] 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] A Non-Ambiguous Decomposition of Regular Languages and Factorizing Codes. Discrete Appl. Math. 126 (2003) 129-165. | Zbl
,[3] Theory of Codes. Academic Press, New York (1985). | MR | Zbl
and ,[4] Trends in the Theory of Codes. Bull. EATCS 29 (1986) 84-95. | Zbl
and ,[5] Rational Series and Their Languages. EATCS Monogr. Theoret. Comput. Sci. 12 (1988). | MR | Zbl
and ,[6] Une famille remarquable de codes indécomposables, in Proc. Icalp 78. Lect. Notes Comput. Sci. 62 (1978) 105-112. | Zbl
,[7] Sur les codes factorisants1980) 1-8.
,[8] Synchronization and decomposability for a family of codes. Intern. J. Algebra Comput. 4 (1992) 367-393. | Zbl
and ,[9] Synchronization and decomposability for a family of codes: Part 2. Discrete Math. 140 (1995) 47-77. | Zbl
and ,[10] Variable-Length Maximal Codes, in Proc. Icalp 96. Lect. Notes Comput. Sci. 1099 (1996) 24-47. | Zbl
and ,[11] Indecomposable prefix codes and prime trees, in Proc. DLT 97 edited by S. Bozapadilis-Aristotel (1997).
, and ,[12] Sur un algorithme donnant les codes bipréfixes finis. Math. Syst. Theory 6 (1972) 221-225. | Zbl
,[13] 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] Construction of a family of finite maximal codes. Theoret. Comput. Sci. 63 (1989) 157-184. | Zbl
,[15] A partial result about the factorization conjecture for finite variable-length codes. Discrete Math. 122 (1993) 137-152. | Zbl
,[16] An application of Hajós factorizations to variable-length codes. Theoret. Comput. Sci. 164 (1996) 223-252. | Zbl
,[17] Factorizing Codes and Schützenberger Conjectures, in Proc. MFCS 2000. Lect. Notes Comput. Sci. 1893 (2000) 295-303. | Zbl
,[18] On some Schützenberger Conjectures. Inform. Comp. 168 (2001) 144-155. | Zbl
,[19] An enhanced property of factorizing codes. Theor. Comput. Sci. 340 (2005) 240-256. | Zbl
,[20] Some results on finite maximal codes. RAIRO-Inform. Theor. Appl. 19 (1985) 383-403. | Numdam | Zbl
and ,[21] Solution partielle de la conjecture de factorisation des codes. C.R. Acad. Sci. Paris 302 (1986) 169-170. | Zbl
and ,[22] A three-word code which is not prefix-suffix composed. Theor. Comput. Sci. 163 (1996) 145-160. | Zbl
,[23] Abelian groups. Pergamon Press, New York (1960). | MR | Zbl
,[24] Sur la factorisation des groupes abéliens. Casopis Pest. Mat. Fys. 74 (1950) 157-162. | Zbl
,[25] Sur une propriété des polynômes de la division du cercle. C.R. Acad. Sci. Paris 240 (1937) 397-399. | JFM
and ,[26] A note on codes having no finite completions. Inform. Proc. Lett. 55 (1995) 185-188. | Zbl
,[27] Hajós factorizations and completion of codes. Theor. Comput. Sci. 182 (1997) 245-256. | Zbl
,[28] Locally complete sets and finite decomposable codes. Theor. Comput. Sci. 273 (2002) 185-196. | Zbl
and ,[29] É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] Codes asynchrones. Bull. Soc. Math. France 105 (1977) 385-404. | Numdam | Zbl
,[31] Polynôme d'un code1980) 169-176.
,[32] 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
and ,[33] On codes having no finite completions. Discrete Math. 17 (1977) 309-316. | Zbl
,[34] Codes and local constraints. Theor. Comput. Sci. 72 (1990) 55-64. | Zbl
,[35] Completing codes. RAIRO-Inf. Theor. Appl. 23 (1989) 135-147. | Numdam | Zbl
, and ,[36] On the lattice of prefix codes. Theor. Comput. Sci. 289 (2002) 755-782. | Zbl
and ,[37] Sulla fattorizzazione dei codici. Ricerche di Mat. XXXII (1983) 115-130. | Zbl
,[38] Non commutative factorization of variable-length codes. J. Pure Appl. Algebra 36 (1985) 167-186. | Zbl
,[39] On the factorisation of finite abelian groups. Acta Math. Acad. Sci. Hungaricae 8 (1957) 65-86. | Zbl
,[40] Une théorie algébrique du codage, Séminaire Dubreil-Pisot 1955-56, exposé No. 15 (1955), 24 p. | Numdam
,[41] Construction de codes indécomposables. RAIRO-Inf. Theor. Appl. 19 (1985) 165-178. | Numdam | Zbl
,[42] Two classes of factorizing codes - -codes and -codes, in Words, Languages and Combinatorics II, edited by M. Ito and H. Jürgensen. World Scientific (1994) 477-483. | Zbl
and ,Cité par Sources :