Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \newcommand{\przesun}{{\hspace*{0.3in}}}% \newcommand{\dB}{\mbox{\sf deBr}}% \newcommand{\DB}{\mathbf{DB}}% \newcommand{\C}[2]{{\mathcal{C}}_{#1}(#2)}% \newcommand{\Cfact}{\mathit{Cfact}}% \newcommand{\Shift}{\mathit{Shift}}% \newcommand{\Bi}{\mathtt{B}} $

$\Shift(\sa{001011101}, \sa{0111}) = \sa{010010111}$ and $\Shift(\sa{001011101}, \sa{1010}) = \sa{010111010}$.

With $n=2$, $\sa{0010} \oplus \sa{1101} = \sa{0010}\,\sa{1110}$, since $\Shift(\sa{1101}, \sa{10}) = \sa{1110}$.

$\Psi(\sa{0010111011}) = \sa{0011010010}$.

For the de Bruijn word $\sa{0011}$, we have $\Psi(\sa{0011})=\sa{0010}$ and $\overline{\Psi(\sa{0011})}=\sa{1101}$. Then $\sa{0010} \oplus \sa{1101} = \sa{0010}\,\sa{1110}$, which is a de Bruijn word of length $8$.

Problem 118: Recursive Generation of de Bruijn Words

Following Problem 117, the present problem provides another method to generate a de Bruijn word on the alphabet $\Bi = \{\sa{0},\sa{1}\}$. The method is recursive and its description requires a few preliminary definitions.

Let us first define $\Shift$. When a word $u$ occurs circularly exactly once in a word $x$, $|u|\lt |x|$, $\Shift(x,u)$ denotes the conjugate of $x$ admitting $u$ as a suffix.

Let us then define the operation $\oplus$ between two words $x,y\in \Bi^N$, $N={2^n}$, for which the suffix $u$ of length $n$ of $x$ has a unique circular factor occurrence in $y$: $x \oplus y$ denotes $x\cdot \Shift(y,u)$.

Eventually, for a binary word $w$, let $\Psi(w)$ be the binary word $v$ of length $|w|$ defined, for $0 \leq i \leq |w|-1$, by $$v[i] = (w[0]+w[1]+ \cdots +w[i]) \bmod 2.$$ Also denote by $\overline{x}$ the complement of $x$, that is, its bitwise negation.

Show that if $x$ is a binary de Bruijn word of length $2^n$ then $\Psi(x) \oplus \overline{\Psi(x)}$ is a de Bruijn word of length $2^{n+1}$.

Count circular factors of $\Psi(x) \oplus \overline{\Psi(x)}$.

References

S. W. Golomb. Shift Register Sequences. World Scientific, Singapore, 2017. Third revised edition.

A. Lempel. On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers. IEEE Trans. Computers, 19(12):1204-1209, 1970.

D. Repke and W. Rytter. On semi-perfect de Bruijn words. Theor. Comput. Sci., 720:55-63, 2018.

125 Problems in Text Algorithms

Example

Problem 118: Recursive Generation of de Bruijn Words

References