%I #11 Dec 08 2022 11:04:15
%S 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
%N 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.
%C The growth is bounded by 1/30*110^(n/42) <= DupRoots(n) <= 2^n.
%C Duplication on strings was originally motivated by the fact that it occurs in DNA strands.
%D J. Dassow, V. Mitrana, and G. Păun, On the regularity of duplication closure. Bulletin of the EATCS, 69 1999, pp. 133-136.
%D 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.
%H Peter Leupold, <a href="http://www.wortspieler.org/Dateien/Pubs/09DupAlgo.pdf">Reducing Repetitions</a>, Stringology (Aug 2009), pp. 225-236.
%e The shortest word with ambiguous root (up to reversal and renaming of letter) is
%e .abcbabcbc
%e which can be reduced to the words
%e .abc, abcbc, abcbabc, abcbabcbc
%e and of these only
%e .abc, abcbabc
%e are squarefree.
%e Witnesses for the value changes from 2 to 4 and from 4 to 5 are
%e .DUPROOT(abcbabcbcacbca) = (abcbabcacbca, abcbabca, abcacbca, abca).
%e .DUPROOT(ababcbabcacbabcabacbabcab) = (abcbabcabacbabcab, abcbabcab, abcacbabcab, abcabacbabcab, abcab).
%e Words with three roots exist, however, the first one is longer than the first one with four roots:
%e .DUPROOT(babacabacbcabacb) = (bacabacb, bacbcabacb, bacb).
%K hard,more,nonn,nice
%O 1,9
%A Peter Leupold (leupold(AT)cc.kyoto-su.ac.jp), May 23 2009