Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-16T07:26:53.158Z Has data issue: false hasContentIssue false
  • English
  • Français

Uniformly bounded duplication codes

Published online by Cambridge University Press:  17 August 2007

Peter Leupold  and
Victor Mitrana
Peter Leupold
Affiliation:
Research Group in Mathematical Linguistics, Rovira i Virgili University, Pça. Imperial Tàrraco 1, 43005 Tarragona, Catalunya, Spain; [email protected]; [email protected]
Victor Mitrana
Affiliation:
Research Group in Mathematical Linguistics, Rovira i Virgili University, Pça. Imperial Tàrraco 1, 43005 Tarragona, Catalunya, Spain; [email protected]; [email protected] Faculty of Mathematics and Computer Science, Bucharest University, Str. Academiei 14, 70109 Bucureşti, Romania.
Get access

Abstract

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.

Keywords

Duplicationduplication primitive wordduplication rootduplication code
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 4 , October 2007 , pp. 411 - 424
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985).
Dassow, J., Mitrana, V. and Păun, Gh., On the Regularity of Duplication Closure. Bull. EATCS 69 (1999) 133–136.
Fine, N. and Wilf, H., Uniqueness Theorems for Periodic Functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. CrossRef
International Human Genome Sequencing Consortium, Finishing, the Euchromatic Sequence of the Human Genome. Nature 431 (2004) 931–945.
Leupold, P., Mitrana, V. and Sempere, J., 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. CrossRef
Leupold, P., Martín Vide, C. and Mitrana, V., Uniformly Bounded Duplication Languages. Discrete Appl. Math. 146 (2005) 301–310. CrossRef
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983).
Ross, R. and Winklmann, K., Repetitive Strings are not Context-Free. RAIRO-Theor. Inf. Appl. 16 (1982) 191–199.
A. Salomaa, Formal Languages. Academic Press, Orlando (1973).
H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung (1991).
Wang, M.-W., On the Irregularity of the Duplication Closure. Bull. EATCS 70 (2000) 162–163.