5
$\begingroup$

Does there exist an infinite binary sequence $B$ that satisfies all of the following three properties?

  1. It is possible to prove that for any integer $n$ the initial $2^{n+1}$ bits of $B$ contain all $n$-bit words, i.e. if $B_n$ is a word corresponding to the initial $2^{n+1}$ bits of $B$, then any $n$-bit word $w$ is a substring (a contiguous subsequence) of $B_n$;
  2. $B$ is efficiently computable, i.e. there exists an efficient generalized algorithm that, given an arbitrary integer $m$, outputs the initial $m$ bits of $B$ (or the $m$-th bit of $B$);
  3. The construction of $B$ is not based on the concatenation of de Bruijn sequences.

An example of a sequence that satisfies the first two properties is $$\text{01 0011 00010111 0000100110101111} \ldots,$$

which is the concatenation of the lexicographically first $2$-ary de Bruijn sequences of order $1,2,3,4$ etc.

$\endgroup$
0

0

You must log in to answer this question.

Browse other questions tagged .