The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (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)
 OFFSET 1,9 COMMENTS 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. REFERENCES J. Dassow, V. Mitrana, and G. Păun, On the regularity of duplication closure. Bulletin of the EATCS, 69 1999, pp. 133-136. Peter 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. LINKS Table of n, a(n) for n=1..25. Peter Leupold, Reducing Repetitions, Stringology (Aug 2009), pp. 225-236. EXAMPLE The shortest word with ambiguous root (up to reversal and renaming of letter) is .abcbabcbc 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). CROSSREFS Sequence in context: A294078 A064133 A295101 * A105674 A130496 A187243 Adjacent sequences: A160672 A160673 A160674 * A160676 A160677 A160678 KEYWORD hard,more,nonn,nice AUTHOR Peter Leupold (leupold(AT)cc.kyoto-su.ac.jp), May 23 2009 STATUS approved

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

Last modified September 11 23:02 EDT 2024. Contains 375842 sequences. (Running on oeis4.)