A339391 Maximum, over all binary strings w of length n, of the size of the smallest string attractor for w.

1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5

Offset

1,2

Comments

A set S of positions of a string w[1..n] is called a "string attractor" if every nonempty contiguous block occurring in w has an occurrence in w that touches at least one of the positions of S. For example, "alfalfa" has a string attractor of size 3: {3,4,5}.

0 has smallest string attractor size 1;

01 has smallest string attractor size 2;

001011 has smallest string attractor size 3;

000100101011 has smallest string attractor size 4;

0001001010110111 has smallest string attractor size 5.

These are the shortest binary strings achieving this minimum attractor size.

Links

Table of n, a(n) for n=1..19.

D. Kempa and N. Prezza. At the roots of dictionary compression: string attractors. In STOC'18 Proceedings, ACM Press, 2018, pp. 827-840.

Prog

(Python)
from itertools import product, combinations
def blocks_ranges(w):
  blocks = dict()
  for i in range(len(w)):
    for j in range(i+1, len(w)+1):
      wij = w[i:j]
      if wij in blocks: blocks[wij].append(set(range(i, j)))
      else: blocks[wij] = [set(range(i, j))]
  return blocks
def is_attractor(S, w):
  br = blocks_ranges(w)
  for b in br:
    for i in range(len(br[b])):
      if S & br[b][i]: break
    else: return False
  return True
def lsa(w): # length of smallest attractor of w
  for r in range(1, len(w)+1):
    for s in combinations(range(len(w)), r):
      if is_attractor(set(s), w): return r
def a(n):   # only search strings starting with 0 by symmetry
  return max(lsa("0"+"".join(u)) for u in product("01", repeat=n-1))
print([a(n) for n in range(1, 12)]) # Michael S. Branicky, Dec 20 2020

Crossrefs

Sequence in context: A097429 A100617 A076471 * A165116 A111656 A165118

Adjacent sequences: A339388 A339389 A339390 * A339392 A339393 A339394

Keyword

nonn,more

Author

Jeffrey Shallit, Dec 12 2020

Extensions

(17)-a(19) from Michael S. Branicky, Dec 20 2020

Status

approved