On the longest common subsequence of Thue-Morse words
share
The length a(n) of the longest common subsequence of the n'th Thue-Morse word and its bitwise complement is studied. An open problem suggested by Jean Berstel in 2006 is to find a formula for a(n). In this paper we prove new lower bounds on a(n) by explicitly constructing a common subsequence between the Thue-Morse words and their bitwise complement. We obtain the lower bound a(n) = 2^n(1-o(1)), saying that when n grows large, the fraction of omitted symbols in the longest common subsequence of the n'th Thue-Morse word and its bitwise complement goes to 0. We further generalize to any prefix of the Thue-Morse sequence, where we prove similar lower bounds.
READ FULL TEXT