1
$\begingroup$

A DeBruijn sequences of order $n$ encodes all possible strings of length $n$ over an alphabet with $k$ symbols and algorithms for their construction are well known among those familiar with the subject; see for example this MO question.

Question:

Given a fixed collection of sets of length $n$ strings over an alphabet with $k$ symbols:

  • (when) is it possible to find a (minimal) set of additional length $n$ strings that, when added (possibly with repetitions) to the given collection of sets, allows it to encode each set in a DeBruijn-like manner, i.e. in each of the generated (cyclic) sequences $n$ adjacent symbols either resemble an element of the encoded set or an element of the additional set?

  • provided the existence of such sequences: is it possible to construct them to optimality, i.e., either minimizing the maximal length of the set-encoding strings or minizing their summed lengths.

Remark:
In the encoding of the sets uniqueness of the elements is not required; especially if non-uniqueness allows more compact overall encoding of the sets.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.