De Bruijn Sequence and Universal Cycle Constructions

Concatentation Method Output
Algorithm
Order $n$
Alphabet size $k$
Constructing DB sequences using concatenation approaches

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$:

Granddaddy Concatenation Construction
  1. List the necklaces of length $n$ with alphabet size $k$ in lex order.
  2. Concatenate together the longest aperiodic prefixes of each necklace.
For example, for $n=5$ and $k=2$ we obtain the DB sequence:

          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].

Grandmama Concatenation Construction
  1. List the necklaces of length $n$ with alphabet size $k$ in colex order.
  2. Concatenate together the longest aperiodic prefixes of each necklace.
For $n=5$ and $k=2$, we obtain:

          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.

A generic approach

The above concatenation strategies can be stated more generally for an arbitrary non-singular feedback function $f$.

Generic Concatenation Approach
  1. Order the equivalence classes induced by the feedback function $f$.
  2. Concatenate together defined representatives for each cycle of an equivalence class.
Applying this approach in the binary case, using the Complementing Cycling Register (CCR) for $f$, we obtain the following equivalence classes ordered in lex order with respect to their lex smallest element.

If the cycles are represented by their lex smallest rotation (the blue columns read top to bottom), then the concatenation approach yields the following sequence:

          0000011111 0001011101 0010011011 01.

Since the substring 11010 appears twice (once in wraparound), this is not a DB sequence. However, if the classes are re-ordered 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:

  1. $1 \leq r \leq k{-}1$ and $r$ is coprime with $k$, and
  2. $0 \leq s \leq k{-}1$ and ($r=1$ or $s$ is coprime with $k$)

Lexicographic compositions

An early attempt to find an efficient shift-rule for the binary Prefer-same 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.

Cool-lex order

Using cool-lex order for binary strings, an underlying concatenation scheme is used to construct a dual-density 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.

References

  • [FK77] H. Fredricksen and I. Kessler. Lexicographic compositions and deBruijn sequences. J. Combinatorial Theory Ser. A, 22(1):17-30, 1977.

  • [FM78] H. Fredricksen and J. Maiorana. Necklaces of beads in $k$ colors and $k$-ary de Bruijn sequences. Discrete Math., 23(3):207-210, 1978.

  • [DHS+18] P. B. Dragon, O. I. Hernandez, J. Sawada, A. Williams, and D. Wong. Constructing de Bruijn sequences with co-lexicographic order: the $k$-ary Grandmama sequence. European J. Combin., 72:1-11, 2018.

  • [DHW16] P. B. Dragon, O. I. Hernandez, and A. Williams. The grandmama de Bruijn sequence for binary strings. In LATIN 2016: theoretical informatics, volume 9644 of Lecture Notes in Comput. Sci., pages 347-361. Springer, Berlin, 2016.

  • [GS17] D. Gabric and J. Sawada. A de Bruijn sequence construction by concatenating cycles of the complemented cycling register. In Combinatorics on words, volume 10432 of Lecture Notes in Comput. Sci., pages 49-58. Springer, Cham, 2017.

  • [GS18] D. Gabric and J. Sawada. Constructing de Bruijn sequences by concatenating smaller universal cycles. Theoret. Comput. Sci., 743:12-22, 2018.

  • [RSW92] F. Ruskey, C. Savage, and T. M. Y. Wang. Generating necklaces. J. Algorithms, 13(3):414-430, 1992.

  • [RSW12] F. Ruskey, J. Sawada, and A. Williams. De Bruijn sequences for fixed-weight binary strings. SIAM J. Discrete Math., 26(2):605-617, 2012.