Binary Shift Rule  Output  

Let $\mathbf{B}(n)$ denote the set of binary strings of length $n$. A function $f : \mathbf{B}(n) \rightarrow \{0,1\}$ is a DBsuccessor if there exists a DB sequence $\mathcal{D}$ such that each string $\alpha = a_1a_2\cdots a_n \in \mathbf{B}(n)$ is followed by the symbol $f(\alpha)$ in $\mathcal{D}$. In the best case, such a successor will run in $O(n)$ time per symbol generated using $O(n)$ space. Each such DBsuccessor is based on an underlying feedback function $g$ which partitions the de Bruijn graph $G(n{}1,k)$ into a factor of small cycles. Then, special conditions are determined for joining the small cycles together. This approach is similar to Hierholzer's algorithm for generating an Euler cycle. Generally, the simpler the feedback function the simpler the conditions for a related DBsuccessor. The following are among the simplest feedback functions where $\oplus$ denote addition mod 2:
Using the PCR as the underlying feedback function to initially partition $\mathbf{B}(n)$ into smaller cycles, the following four simple DBsuccessors are obtained [GSWW18]. These rules test whether or not a string is a necklace, which is a string that is lexicographically smallest amongst all its rotations. This can be done in $O(n)$ time. The shift rule for the Granddaddy [Fre72] corresponds to the lexicographically smallest binary DB sequence that can also be constructed by the Prefersmallest greedy approach and a concatenation construction. The Grandmama [DHS+18] can also be constructed via a concatenation construction.
$f(\alpha) = \left\{ \begin{array}{ll} \overline{a}_1 &\ \ \mbox{if $\color{blue}{a_ja_{j+1}\cdots a_n 0 1^{j2}}$ is a necklace;}\\ {a_1} \ &\ \ \mbox{otherwise,}\end{array} \right.$
where $j$ is the smallest index of $\alpha$ such that $a_j = 0$ and $j > 1$, or $j=n{+}1$ if no such index exists.
$f(\alpha) = \left\{ \begin{array}{ll} \overline{a}_1 &\ \ \mbox{if $\color{blue}{0^{nj}1a_2\cdots a_j}$ is a necklace;}\\ {a_1} \ &\ \ \mbox{otherwise,}\end{array} \right.$
where $j$ is the largest index of $\alpha$ such that $a_j = 1$, or $j=0$ if no such index exists.
The following two successors are perhaps the simplest to state DBsuccessors. The PCR3 DBsuccessor [SWW16b] is a special case of a more generic DBsuccessor [JFB91].
$ f(\alpha) = \left\{ \begin{array}{ll} \overline{a}_1 &\ \ \mbox{if $\color{blue}{a_2a_3\cdots a_n1}$ is a necklace;}\\ {a_1} \ &\ \ \mbox{otherwise.}\end{array} \right.$
$f(\alpha) = \left\{ \begin{array}{ll} \overline{a}_1 &\ \ \mbox{if $\color{blue}{0a_2 a_3 \cdots a_{n}}$ is a necklace;}\\ {a_1} \ &\ \ \mbox{otherwise.}\end{array} \right.$
Using the CCR as the underlying feedback function, the following three simple DBsuccessors are obtained [GSWW18]. A string $\gamma$ is a conecklace if $\gamma \overline{\gamma}$ is a necklace.
$f(\alpha) = \left\{ \begin{array}{ll} a_1 &\ \ \mbox{if $\color{blue}{a_ja_{j+1}\cdots a_n 1 0^{j2}}$ is a conecklace;}\\ \overline{a}_1 \ &\ \ \mbox{otherwise.}\end{array} \right.$
where $j$ is the smallest index of $a_2a_3\cdots a_n$ such that $a_j = 0$, or $j=n{+}1$ if no such index exists.
$f(\alpha) = \left\{ \begin{array}{ll} a_1 &\ \ \mbox{if $\color{blue}{0^{nj}1\overline{a}_2 \overline{a}_3\cdots \overline{a}_{j}}$ is a conecklace;}\\ \overline{a}_1 \ &\ \ \mbox{otherwise.}\end{array} \right.$
where $j$ is the largest index of $\alpha$ such that $a_j = 1$, or $j=n$ if no such index exits
$f(\alpha) = \left\{ \begin{array}{ll} a_1 &\ \ \mbox{if $\color{blue}{a_2 a_3 \cdots a_{n}0}$ is a conecklace not equal to $0^n$;}\\ \overline{a}_1 \ &\ \ \mbox{otherwise.}\end{array} \right.$
Like PCR3, the CCR3 DBsuccesor is an efficient application of the more generic rule by [JFB91]. The DBsuccessor given by Huang [Hua90] is also based on the CCR, however, it is more complicated. Etzion [Etz87] also presented a DBsuccessor based on the CCR, but it is also more complex and has yet to be implemented.
By considering the PRR as the underlying feedback function, the underlying structure of the greedy Prefersame and Preferopposite constructions have been unveiled [SSA20]. These sequences are the lexicographically largest and smallest sequences, respectively, with respect to their runlength encoding [ASS21]. Below are two additional constructions related to each sequence. They are used as building blocks to defining the successors. Each of the following six DBsuccessors can be implemented in $O(n)$ time per symbol generated using $O(n)$ space.
Prefersame: Consider the following three representatives for equivalence classes induced by the PRR, where a string is said to be special if it begins and ends with 0 and has runlength encoding of the form $(21^{2x})^y1^z, \mbox{where $x \geq 0$, $y\geq 2$, and $z\geq 2$}.$
$f(\alpha) = \left\{ \begin{array}{ll} a_1 \oplus a_2 \oplus a_n \oplus 1 &\ \ \mbox{if $\color{blue}{0a_2 a_3 \cdots a_{n}}$ or $\color{blue}{1a_2 a_3 \cdots a_{n}}$ is an RLrep;}\\ a_1 \oplus a_2 \oplus a_n\ &\ \ \mbox{otherwise.}\end{array} \right.$
The following successor can be used to construct the lexicographic composition concatenation construction [FK77].
$f(\alpha) = \left\{ \begin{array}{ll} a_1 \oplus a_2 \oplus a_n \oplus 1 &\ \ \mbox{if $\color{blue}{0a_2 a_3 \cdots a_{n}}$ or $\color{blue}{1a_2 a_3 \cdots a_{n}}$ is an LCrep;}\\ a_1 \oplus a_2 \oplus a_n \ &\ \ \mbox{otherwise.}\end{array} \right.$
$f(\alpha) = \left\{ \begin{array}{ll} a_1 \oplus a_2 \oplus a_n \oplus 1 &\ \ \mbox{if $\color{blue}{0a_2 a_3 \cdots a_{n}}$ or $\color{blue}{1a_2 a_3 \cdots a_{n}}$ is a samerep;}\\ a_1 \oplus a_2 \oplus a_n \ &\ \ \mbox{otherwise.}\end{array} \right.$
Preferopposite: Consider the following three representatives for equivalence classes induced by the PRR, where a string is said to be special2 if it begins with 10 and has runlength encoding of the form $1x^t y, \mbox{where $t$ is odd and $y>x$}.$
$f(\alpha) = \left\{ \begin{array}{ll} a_1 \oplus a_2 \oplus a_n \oplus 1 &\ \ \mbox{if $\color{blue}{0a_2 a_3 \cdots a_{n}}$ or $\color{blue}{1a_2 a_3 \cdots a_{n}}$ is an RL2rep;}\\ a_1 \oplus a_2 \oplus a_n\ &\ \ \mbox{otherwise.}\end{array} \right.$
$f(\alpha) = \left\{ \begin{array}{ll} a_1 \oplus a_2 \oplus a_n \oplus 1 &\ \ \mbox{if $\color{blue}{0a_2 a_3 \cdots a_{n}}$ or $\color{blue}{1a_2 a_3 \cdots a_{n}}$ is an LC2rep;}\\ a_1 \oplus a_2 \oplus a_n \ &\ \ \mbox{otherwise.}\end{array} \right.$
$f(\alpha) = \left\{ \begin{array}{ll} a_1 \oplus a_2 \oplus a_n \oplus 1 &\ \ \mbox{if $\color{blue}{0a_2 a_3 \cdots a_{n}}$ or $\color{blue}{1a_2 a_3 \cdots a_{n}}$ is an oppositerep;}\\ a_1 \oplus a_2 \oplus a_n \ &\ \ \mbox{otherwise.}\end{array} \right.$