A160675 - 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