This site is supported by donations to The OEIS Foundation.



Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A160675 Duplication root: the maximal number of distinct squarefree words that a word of length n can be reduced to by iterated application of string-rewriting rules uu->u. 0
1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5 (list; graph; refs; listen; history; text; internal format)



The growth is bounded by 1/30*110^(n/42) <= DupRoots(n) <= 2^n.

Duplication on strings was originally motivated by the fact that it occurs in DNA strands.


J. Dassow, V. Mitrana, and G. Păun, On the regularity of duplication closure. Bulletin of the EATCS, 69 1999, pp. 133-136.

P. Leupold: Duplication roots, in Developments in Language Theory, T. Harju, J. Karhumski and A. Lepisto, eds., vol. 4588 of Lecture Notes in Computer Science, Springer, 2007, pp. 290-299.

P. Leupold: Reducing Repetitions, Manuscript, 2009.


Table of n, a(n) for n=1..25.

P, Leupold, Manuscript containing the definition and the bounds


The shortest word with ambiguous root (up to reversal and renaming of letter) is


which can be reduced to the words

.abc, abcbc, abcbabc, abcbabcbc

and of these only

.abc, abcbabc

are squarefree.

Witnesses for the value changes from 2 to 4 and from 4 to 5 are

.DUPROOT(abcbabcbcacbca) = (abcbabcacbca, abcbabca, abcacbca, abca).

.DUPROOT(ababcbabcacbabcabacbabcab) = (abcbabcabacbabcab, abcbabcab, abcacbabcab, abcabacbabcab, abcab).

Words with three roots exist, however, the first one is longer than the first one with four roots:

.DUPROOT(babacabacbcabacb) = (bacabacb, bacbcabacb, bacb).


Sequence in context: A164296 A233566 A064133 * A105674 A130496 A187243

Adjacent sequences:  A160672 A160673 A160674 * A160676 A160677 A160678




Peter Leupold (leupold(AT)cc.kyoto-su.ac.jp), May 23 2009



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 20 13:59 EST 2017. Contains 294972 sequences.