Uniformly bounded duplication codes
Leupold, Peter ; Mitrana, Victor
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 411-424 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Duplication is the replacement of a factor w within a word by ww. 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.

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007021
Classification:  68R15,  68Q45,  94B60 
@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},
     volume = {41},
     year = {2007},
     pages = {411-424},
     doi = {10.1051/ita:2007021},
     mrnumber = {2377971},
     zbl = {pre05301989},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 411-424. doi : 10.1051/ita:2007021. http://gdmltest.u-ga.fr/item/ITA_2007__41_4_411_0/

[1] J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985). | MR 797069 | Zbl 0587.68066

[2] J. Dassow, V. Mitrana and Gh. Păun, On the Regularity of Duplication Closure. Bull. EATCS 69 (1999) 133-136. | Zbl 0941.68605

[3] N. Fine and H. Wilf, Uniqueness Theorems for Periodic Functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | Zbl 0131.30203

[4] International Human Genome Sequencing Consortium, Finishing the Euchromatic Sequence of the Human Genome. Nature 431 (2004) 931-945.

[5] P. Leupold, V. Mitrana and J. Sempere, 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.

[6] P. Leupold, C. Martín Vide and V. Mitrana, Uniformly Bounded Duplication Languages. Discrete Appl. Math. 146 (2005) 301-310. | Zbl 1077.68047

[7] M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983). | MR 675953 | Zbl 0514.20045

[8] R. Ross and K. Winklmann, Repetitive Strings are not Context-Free. RAIRO-Theor. Inf. Appl. 16 (1982) 191-199. | Numdam | Zbl 0489.68071

[9] A. Salomaa, Formal Languages. Academic Press, Orlando (1973). | MR 438755 | Zbl 0262.68025

[10] H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung (1991). | MR 1090325 | Zbl 0746.20050

[11] M.-W. Wang, On the Irregularity of the Duplication Closure. Bull. EATCS 70 (2000) 162-163. | Zbl 0983.68111