De Bruijn Sequence and Universal Cycle Constructions

Lempel's D-morphism [Lem70] maps a cyclic binary string $\alpha = a_1a_2\cdots a_m$ to $\beta = b_1b_2\cdots b_{m}$ where each $b_i = a_{i} \oplus a_{i+1}$, noting $b_m = a_m \oplus a_1$. Both $\alpha$ and its complement $\overline{\alpha}$ map to the same $\beta$. The inverse of this operation, denoted $\mathcal{L}(\beta)$, is known as Lempel's lift. When the weight (number of 1s) of $\beta$ is even $\mathcal{L}(\beta)$ contains two strings (complements); when the weight is odd, it contains one string rotationally equivalent to its complement.

When $\beta = b_1b_2\cdots b_m$ is a universal cycle (UC) of order $n$ for a set $\mathbf{S}$ consisting of $m$ binary strings then:

1. If $\beta$ has even weight, then $\mathcal{L}(\beta) = \{\alpha_0, \alpha_1\}$ consisting of two disjoint UCs of order $n{+}1$ and length $m$. Each $\alpha_i = a_1a_2\cdots a_m$ where $a_1 = i$ and $a_j = a_{j-1} \oplus b_j$ for $j > 1$.
   
   
2. If $\beta$ has odd weight, then $\mathcal{L}(\beta) = a_1a_2\cdots a_{2m}$ is a single UC of order $n{+}1$ with weight $m$ where $a_1 = 0$ and $a_j = a_{j-1} \oplus b_j$ for $j > 1$ allowing $b_{m+1}\cdots b_{2m} = \beta$.

More generally, for an arbitrary alphabet of size $k>2$, $\mathcal{L}(b_1b_2\cdots b_m) = \{\alpha_0, \alpha_1, \ldots ,\alpha_{k-1}\}$ such that each $\alpha_i = a_1a_2\cdots a_t$ is defined as $a_1 = i$ and $a_j = (a_{j-1} + b_j) \bmod k$ for $j > 1$. Each $t$ is a multiple of $m$ and one or more $\alpha_i$ may correspond to the same cycle (like the odd weight case above).

A punctured DB sequence is a DB sequence with the unique substring $1^n$ replaced with $1^{n-1}$.

Below are two methods that apply the above results to recursively construct DB sequences. Like the Euler cycle and greedy approaches, an exponential amount of space is required by these recursive strategies. Each symbol can be generated in $O(1)$-amortized time, but the first symbol requires exponential time delay. Optimized approaches have been considered [Ann97] along with corresponding successor rules [CPKS99,Knu11].

The two recursive constructions generalize naturally to alphabets of size $k>2$ [AA11,Knu11,NW22] where Lempel's lift will create up to $k$ cycles that can be joined together via alternating strings of length $n-1$. As an example for $k=3$ and $n=8$, possible joining strings are 0120120, 1201201, 2012012.