Duplication is the replacement of a factor within a word by . This operation can be used iteratively to generate languages starting from words or sets of words. By undoing duplications, one can eventually reach a square-free word, the original word’s duplication root. The duplication root is unique, if the length of duplications is fixed. Based on these unique roots we define the concept of duplication code. Elementary properties are stated, then the conditions under which infinite duplication codes exist are fully characterized; the relevant parameters are the duplication length and alphabet size. Finally, some properties of the languages generated by duplication codes are investigated.
Mots-clés : duplication, duplication primitive word, duplication root, duplication code
@article{ITA_2007__41_4_411_0, author = {Leupold, Peter and Mitrana, Victor}, title = {Uniformly bounded duplication codes}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {411--424}, publisher = {EDP-Sciences}, volume = {41}, number = {4}, year = {2007}, doi = {10.1051/ita:2007021}, mrnumber = {2377971}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2007021/} }
TY - JOUR AU - Leupold, Peter AU - Mitrana, Victor TI - Uniformly bounded duplication codes JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2007 SP - 411 EP - 424 VL - 41 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2007021/ DO - 10.1051/ita:2007021 LA - en ID - ITA_2007__41_4_411_0 ER -
%0 Journal Article %A Leupold, Peter %A Mitrana, Victor %T Uniformly bounded duplication codes %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2007 %P 411-424 %V 41 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2007021/ %R 10.1051/ita:2007021 %G en %F ITA_2007__41_4_411_0
Leupold, Peter; Mitrana, Victor. Uniformly bounded duplication codes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 4, pp. 411-424. doi : 10.1051/ita:2007021. http://archive.numdam.org/articles/10.1051/ita:2007021/
[1] Theory of Codes. Academic Press, Orlando (1985). | MR | Zbl
and ,[2] On the Regularity of Duplication Closure. Bull. EATCS 69 (1999) 133-136. | Zbl
, and ,[3] Uniqueness Theorems for Periodic Functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | Zbl
and ,[4] International Human Genome Sequencing Consortium, Finishing the Euchromatic Sequence of the Human Genome. Nature 431 (2004) 931-945.
[5] Languages Arising from Gene Repeated Duplication, in Aspects of Molecular Computing. Essays Dedicated to Tom Head on the Occasion of his 70th Birthday. Lect. Notes Comput. Sci. 2950 (2004) 297-308.
, and ,[6] Uniformly Bounded Duplication Languages. Discrete Appl. Math. 146 (2005) 301-310. | Zbl
, and ,[7] Combinatorics on Words. Addison-Wesley, Reading, MA (1983). | MR | Zbl
,[8] Repetitive Strings are not Context-Free. RAIRO-Theor. Inf. Appl. 16 (1982) 191-199. | Numdam | Zbl
and ,[9] Formal Languages. Academic Press, Orlando (1973). | MR | Zbl
,[10] Free Monoids and Languages. Hon Min Book Company, Taichung (1991). | MR | Zbl
,[11] On the Irregularity of the Duplication Closure. Bull. EATCS 70 (2000) 162-163. | Zbl
,Cité par Sources :