Binary Successor 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}$. Each DBsuccessor is based on an underlying feedback function which partitions the de Bruijn graph $G(n{}1,k)$ into a factor of small cycles. Then, simple parentrules are applied to join the small cycles together via conjugate pairs (two length $n$ strings differing in the first symbol) to construct a cyclejoining tree. This approach is similar to Hierholzer's algorithm for generating an Euler cycle. As an example, the following figure illustrates four PCRbased cyclejoining trees created via simple parent rules, where the nodes (necklaces) are cyclic.
Each corresponding DB successor (outlined in the next section) will run in $O(n)$ time per symbol generated using $O(n)$ space; however, there is also a corresponding concatenation tree approach that allows for a more efficient generation of the corresponding DB sequence. Below, we provide DBsuccessors derived from the cyclejoining approach applied to simple feedback functions.
DBsuccessors based on the PCR
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 successor 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.$
DBsuccessors based on the CCR
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 DBsuccessor 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.
DBsuccessors based on the PRR
By considering the PRR as the underlying feedback function, the underlying structure of the greedy Prefersame and Preferopposite constructions has 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 define 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 a runlength encoding of the form $(21^{2x})^y1^z, \mbox{where $x \geq 0$, $y\geq 2$, and $z\geq 2$}.$
 RLrep: The string with the lexicographically largest runlength encoding; if there are two such strings it is the one beginning with 1.
 LCrep: The string $\omega$ such that $t{+}1$ applications of the PRR starting with $\omega$ yields the RLrep, where $t$ is the number of consecutive 1s at the end of the runlength encoding of the RLrep.
 samerep: $\left\{ \begin{array}{ll} \mbox{RLrep} &\ \ \mbox{if the RLrep is special}\\ \mbox{LCrep}\ &\ \ \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 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 a runlength encoding of the form $1x^t y, \mbox{where $t$ is odd and $y>x$}.$
 RL2rep: The string with the lexicographically smallest runlength encoding; if there are two such strings it is the one beginning with 0.
 LC2rep: The string $\omega$ such that $t$ applications of the PRR starting with $\omega$ yields the RL2rep, where $t$ is the last value in the runlength encoding of the RL2rep.
 oppositerep: $\left\{ \begin{array}{ll} \mbox{RL2rep} &\ \ \mbox{if the RL2rep is special2}\\ \mbox{LC2rep}\ &\ \ \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 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.$
 [ASS21] A. Alhakim, E. Sala, and J. Sawada. Revisiting the Prefersame and Preferopposite de Bruijn sequence constructions. Theoretical Computer Science, 852:73–77, 2021.
 [DHS+18] P. B. Dragon, O. I. Hernandez, J. Sawada, A. Williams, and D. Wong. Constructing de Bruijn sequences with colexicographic order: the $k$ary Grandmama sequence. European J. Combin., 72:111, 2018.
 [Etz87] T. Etzion. Selfdual sequences. J. Combin. Theory Ser. A, 44(2):288298, 1987.
 [Fre72] H. Fredricksen. Generation of the Ford sequence of length $2n$; $n$ large. J. Combinatorial Theory Ser. A, 12:153154, 1972.
 [FK77] H. Fredricksen and I. Kessler. Lexicographic compositions and de Bruijn sequences. J. Combinatorial Theory Ser. A, 22(1):1730, 1977.
 [GSWW18] D. Gabric, J. Sawada, A. Williams, and D. Wong. A framework for constructing de Bruijn sequences via simple successor rules. Discrete Math., 341(11):29772987, 2018.
 [Hua90] Y. J. Huang. A new algorithm for the generation of binary de Bruijn sequences. J. Algorithms, 11(1):4451, 1990.
 [JFB91] C. J. A. Jansen, W. G. Franx, and D. E. Boekee. An efficient algorithm for the generation of de Bruijn cycles. IEEE Trans. Inform. Theory, 37(5):14751478, 1991.
 [SSA20] E. Sala, J. Sawada, A. Alhakim. Efficient constructions of the Prefersame and Preferopposite de Bruijn sequences. arXiv preprint arXiv:2010.07960, 2020.
 [SWW16b] J. Sawada, A. Williams, and D. Wong. A surprisingly simple de Bruijn sequence construction. Discrete Math., 339(1):127131, 2016.