Concatentation Method  Output  

Concatenation constructions have led to the most efficient algorithms to construct DB sequences, with some obtaining $O(1)$amortized time per symbol [FM78,DHS+18,GS17]. 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. 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 of length that divides $n$ in lex order. This construction, however, does not generalize to colex order.
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.
More generally, if a feedback function is of the form $f(a_1a_2\cdots a_n) = ra_1 + s$ and using colex order, 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, experimental evidence indicates that there is a simpler shift rule interpretation based on the underlying feedback function $g(a_1a_2\cdots a_n) = a_1 + a_2 + a_n$. Stay tuned.
Using coollex order for binary strings, an underlying concatenation scheme is used to construct a dualdensity DB sequence for bit strings with density $d$ and $d+1$ [RSW12]. A simple strategy for joining these cycles together produceds a DB sequence. More to come.