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 bit $f(\alpha)$ in $\mathcal{D}$. In the best case, such a successor will run in $O(n)$ time per bit using $O(n)$ space. Each such DBsuccessor is based on an underlying feedback function. Generally, the simpler the feedback function the simper the conditions for a related DBsuccessor. The following are the simplest such feedback functions:
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.