| Issue |
RAIRO-Theor. Inf. Appl.
Volume 41, Number 4, October-December 2007
|
|
|---|---|---|
| Page(s) | 411 - 424 | |
| DOI | https://doi.org/10.1051/ita:2007021 | |
| Published online | 17 August 2007 | |
Uniformly bounded duplication codes
1
Research Group in Mathematical Linguistics, Rovira i Virgili University, Pça. Imperial Tàrraco 1, 43005 Tarragona, Catalunya, Spain; klauspeter.leupold@urv.cat; victor.mitrana1@urv.cat
2
Faculty of Mathematics and Computer Science, Bucharest University,
Str. Academiei 14, 70109 Bucureşti, Romania.
Received:
8
September
2005
Accepted:
14
November
2006
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.
Mathematics Subject Classification: 68R15 / 68Q45 / 94B60
Key words: Duplication / duplication primitive word / duplication root / duplication code
© EDP Sciences, 2007
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.