Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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