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

Cité par Sources :