Concatentation Method  Output  

Concatenation constructions [FM78,DHS+18,GS17,GS18] have led to the most efficient algorithms to construct DB sequences, with some obtaining $O(1)$amortized time per symbol. These running times are realized for both the Granddaddy (lex smallest DB sequence) and the Grandmama, which also have $O(n)$time shift rules per symbol.
A necklace is the lexicographically smallest string in an equivalence class under rotation. For instance, such equivalence classes for $n=5$ and $k=2$ are given below, where the top string in each class is a necklace. The classes are listed in lex order with respect to their necklace representative.
The longest aperiodic prefix of each necklace corresponds to the cycle induced by the Pure Cycling Register (PCR). In the above example, the longest aperiodic prefix of each necklace corresponds to the blue bits in each column read top to bottom. The Granddaddy (lex smallest) DB sequence is constructed as follows [FM78] for a given $n,k$:
0 00001 00011 00101 00111 01011 01111 1.
Since necklaces can be generated in lex order in $O(1)$ amortized time [RSW92], the DB sequence can be constructed in $O(1)$ amortized time per each $n$symbols generated. The Granddaddy sequence can also be constructed by the greedy Preferlargest construction and the shift rule PCR1. Amazingly, it took almost 40 years to realize that by replacing lex order with colex order, the concatenation approach will again yield a DB sequence [DHW16,DHW+18].
0 00001 00101 00011 01011 00111 01111 1.
A reason for this late discovery is that the concatenation method for lex order has frequently been described using Lyndon words, which are primitive (aperiodic) necklaces. In particular the Granddaddy corresponds to concatenating all the Lyndon words with length that divides $n$ in lex order. This construction, however, does not generalize to colex order. The Grandmama sequence can also be constructed via the shift rule PCR2.
In addition to these three concatenation constructions, there is a third based on the PCR and two more based on the CCR [GS18]. One of the CCR constructions is outlined next.
The above concatenation strategies can be stated more generally for an arbitrary nonsingular feedback function $f$.
0000011111 0001011101 0010011011 01.
Since the substring 11010 appears twice (once in wraparound), this is not a DB sequence. However, if the classes are reordered using colex order of their lex smallest element at the top of each column, a DB sequence is obtained [GS17,GS18]:
0000011111 0010011011 0001011101 01.
This resulting DB sequence based on the CCR can also be constructed via the shift rule CCR2.
More generally, if a feedback function is of the form $f(a_1a_2\cdots a_n) = ra_1 + s$ and using colex order to order the smaller cycles, then the concatenation approach will produced a DB sequence using the lex smallest cycle representatives if:
An early attempt to find an efficient shiftrule for the binary Prefersame greedy construction resulted in a concatenation construction based on lexicographic compositions [FK77]. The algorithm description is rather complex; however, there is a simpler shift rule interpretation based on the underlying feedback function $f(a_1a_2\cdots a_n) = a_1 + a_2 + a_n$ [SSA20].
Using coollex order for binary strings, an underlying concatenation scheme is used to construct a dualdensity DB sequence for bit strings with density (weight) $d$ and $d+1$ [RSW12]. A simple strategy for joining these cycles together produces a densityrange DB sequence from 0 to $d$. When $d=n$, a DB sequence is produced and can be generated above. The C program available for download can produce both sequences, along with listings of necklaces and Lyndon words in coollex Gray code order.