OFFSET
1,3
COMMENTS
Here "subsequence" means "scattered subsequence" (not necessarily contiguous). A circular word "wraps around".
Slide 10 of Andrew Ryzhikov's talk contains the conjecture that a(n) >= 3n/4, but this conjecture fails for n = 2 and n = 62 (at least). The length-62 counterexample 11111111000000000001010001110110000011010011111001000111010111, where the longest palindromic subsequence is of length 45, was found by Antonio Molina Lovett.
LINKS
Andrew Ryzhikov, Regular subsequences in finite words, talk for the Workshop on Words and Complexity, 19-23 Feb 2018, Villeurbanne, France.
EXAMPLE
Consider the circular word 0001011. A rotation of this circular word gives 0101100, and deleting the first 1 gives the subsequence 001100, which is a palindrome of length 6. This shows that a(7) >= 6.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Sep 05 2018
EXTENSIONS
Terms a(19)-a(32) computed by Antonio Molina Lovett
STATUS
approved