1
$\begingroup$

I am trying to compute the shortest binary string that contains all binary palindrome of length n as substring. For example, for n=3, 00010111 is such a shortest string. However, brutal force performs really bad even for n=6, n=7 etc. Is there any optimization like branch and bound I can do here. My current optimization is following:

  1. Use common super sequence algorithm to get an upper bound of the target string

  2. palindrome of all 0 and all 1 is contained there hence we can place the first n position as 0 and last n position as 1

  3. a continuous block of more than n-2 "1"s or "0"s is clearly not in shortest target string, hence this kind of situation should be avoided.

However, the above optimization is not enough, the program cannot even terminate in reasonable time for n=7.

Hence I am asking if anyone can get some further optimization

$\endgroup$
  • 1
    $\begingroup$ Jeffrey Shallit could work out the case $n=6$. See A330022. $\endgroup$ – Yuval Filmus May 22 at 10:29
  • $\begingroup$ It's not clear to me why (2) holds (i.e., why you can be sure that there is a minimal solution beginning with $n$ 0s and ending with $n$ 1s). Also (3) seems to contradict (2). $\endgroup$ – j_random_hacker May 22 at 23:40
  • $\begingroup$ Have you tried using a SAT solver? $\endgroup$ – D.W. May 23 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.