Is there an efficient way to determine whether a given contiguous sequence can appear within a de Bruijn sequence?

Question

I am curious whether an efficient algorithm exists to determine whether a sequence $S$ can appear within a de Bruijn sequence of order $n$.

For example, for $n=3$, I believe the only de Bruijn sequence is 00010111 (and its rotations/reflection). By definition, any sequence of length $3$ or less will appear at some point, assuming you allow wrapping around or the equivalent. However, 0110 does not appear; you can even prove it cannot fairly easily, as it would still require 111 at some point, granting you a total of 5 1-bits, where the maximum can only be $2^{n-1}=4$ of the 1-bits.

For larger values of $n$ where there are a great many distinct de Bruijn sequences, it seems like deciding whether some sequence may ever appear might turn out to be very difficult to work out. Or perhaps there's some easy trick to it.

If anyone can describe how you could do this/point me towards an algorithm for it, or alternatively confirm that it is difficult after all (in the rough sense of being not computationally feasible past more than the first handful of $n$), I'll consider this answered.

Answer 1

There are many different ways of obtaining de Bruijn sequences, even for the algebraic ones [generate a maximal length sequence and insert a zero to get a string of $n$ zeroes] unless you knew the generating recurrence you wouldn't have a check. You could use Berlekamp Massey to obtain the recurrence and then use the parity check the recurrence represents to rule out the sequence being part of that de Bruijn sequence of order $n.$

So, in general, I strongly believe the answer is no other than checking for violations of the de Bruijn property such as the one you suggested [too many zeroes or ones]. Another possible one is a sequence indicating that there are two $n+1$ sequences which match in the last $n$ symbols.