

A160675


Duplication root: the maximal number of distinct squarefree words that a word of length n can be reduced to by iterated application of stringrewriting 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. 133136.
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. 290299.


LINKS



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



KEYWORD

hard,more,nonn,nice


AUTHOR

Peter Leupold (leupold(AT)cc.kyotosu.ac.jp), May 23 2009


STATUS

approved



