Uniformly bounded duplication codes

Peter Leupold; Victor Mitrana

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 4, page 411-424
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Leupold, Peter, and Mitrana, Victor. "Uniformly bounded duplication codes." RAIRO - Theoretical Informatics and Applications 41.4 (2007): 411-424. <http://eudml.org/doc/249927>.

@article{Leupold2007,
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. },
author = {Leupold, Peter, Mitrana, Victor},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Duplication; duplication primitive word; duplication root; duplication code; square-free word},
language = {eng},
month = {8},
number = {4},
pages = {411-424},
publisher = {EDP Sciences},
title = {Uniformly bounded duplication codes},
url = {http://eudml.org/doc/249927},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Leupold, Peter
AU - Mitrana, Victor
TI - Uniformly bounded duplication codes
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/8//
PB - EDP Sciences
VL - 41
IS - 4
SP - 411
EP - 424
AB - 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.
LA - eng
KW - Duplication; duplication primitive word; duplication root; duplication code; square-free word
UR - http://eudml.org/doc/249927
ER -

References

top
  1. J. Berstel and D. Perrin, Theory of Codes. Academic Press, Orlando (1985).  Zbl0587.68066
  2. J. Dassow, V. Mitrana and Gh. Păun, On the Regularity of Duplication Closure. Bull. EATCS69 (1999) 133–136.  Zbl0941.68605
  3. N. Fine and H. Wilf, Uniqueness Theorems for Periodic Functions. Proc. Amer. Math. Soc.16 (1965) 109–114.  Zbl0131.30203
  4. International Human Genome Sequencing Consortium, Finishing the Euchromatic Sequence of the Human Genome. Nature431 (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.  Zbl1200.68146
  6. P. Leupold, C. Martín Vide and V. Mitrana, Uniformly Bounded Duplication Languages. Discrete Appl. Math.146 (2005) 301–310.  Zbl1077.68047
  7. M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA (1983).  Zbl0514.20045
  8. R. Ross and K. Winklmann, Repetitive Strings are not Context-Free. RAIRO-Theor. Inf. Appl.16 (1982) 191–199.  Zbl0489.68071
  9. A. Salomaa, Formal Languages. Academic Press, Orlando (1973).  Zbl0262.68025
  10. H.J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung (1991).  Zbl0746.20050
  11. M.-W. Wang, On the Irregularity of the Duplication Closure. Bull. EATCS70 (2000) 162–163.  Zbl0983.68111

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.