De Bruijn Sequence and Universal Cycle Constructions

Research problems

  1. Generalize the binary successor rules for the prefer-same and prefer-opposite sequences [SSA20] for $k$-ary alphabets. What is the underlying feedback function?

  2. Is there a simple to understand concatenation construction for the lexicographic composition construction [FK77] of de Bruijn sequences?

  3. Is there a generalization of the lexicographic composition construction [FK77] to $k$-ary alphabets?

  4. Is there a concatenation construction for the simple PCR-based successor rules PCR3 and PCR4 [GSWW18,GSWW20]? If so, state it as simply as possible. What is the underlying ordering of necklaces, and can they be efficiently generated?   Solved!

  5. Can cut-down DB sequences be generated in $O(1)$-amortized time using $O(n)$ space [CGS21,NW22]?   Solved!

  6. Is there a simple successor rule for the greedy XNOR construction [WWW18]?

  7. Construct balanced cut-down DB sequences efficiently by finding a simple successor rule [NW22].

  8. What is the number of distinct balanced cut-down DB sequences for a given length $m$ and alphabet size $k$ [NW22]?

  9. Provide a simple and efficient successor rule for constructing long (aperiodic) orientable sequences, likely based on the cycle joining outlined in [DMRW93]. Can longer (aperiodic) orientable sequences be generated than currently known?   Solved!

  10. Decoding. This website highlights many interesting DB sequence constructions. However, other than a recursive construction, only Granddaddy has been decoded with efficient ranking and unranking algorithms. Find efficient ranking/unranking algorithms for:

    • PCR2- Grandmamma
    • PCR3
    • PCR4
    • Any CCR-based construction
    • Prefer-same
    • Prefer-opposite
    • Cool-lex (binary and more generally fixed-content -- permutations have known efficient ranking).
    • Any cut-down construction
    • Some orientable sequence

  11. Provide an implementation of the recursively generated DB sequences in [Knu11] along with corresponding decoding routines -- see Question 99 on p.317 and the related answers on p.699.

  12. Develop new and interesting applications that apply de Bruijn sequences and universal cycles.

  13. The lexicographically smallest DB sequence (Granddaddy) has many efficient constructions. Does there exist an efficient construction of the lexicographically smallest UC for shorthand permutations? For $n=4$ and $n=5$ they are as follows:

    • $n=4$: 123124132134214324314234
    • $n=5$:
          123412351243124513241325134213452135214321452314231524153215
          342514352435142531453245312541354215432543154235412534152345

  14. Is there an efficient constrution for the lexicographically smallest fixed-density de Bruijn sequence, which is a universal cycle for binary strings with weight $d{-}1$ and $d$ [RSW12]?

  15. Generalize the notion of discrepancy for $k$-ary de Bruijn sequences.

  16. Is there an efficient way to generate a spanning in-tree (arborescence) specifically for the de Bruijn graph? This is the crucial step in Fleury's Euler cycle algorithm to generate a de Bruijn sequence uniformly at random.

References

  • [CGS21] B. Cameron, A. Gündoǧan, and J. Sawada. Cut-down de Bruijn sequences. Manuscript, 2021.

  • [DMRW93] Z.-D. Dai, K. M. Martin, M. J. B. Robshaw, and P. R. Wild. Orientable sequences, Cryptography and Coding III (M.J. Ganley, ed.), Oxford University Press, Oxford, 1993, pp. 97–115.

  • [FK77] H. Fredricksen and I. Kessler. Lexicographic compositions and de Bruijn sequences. J. Combinatorial Theory Ser. A, 22(1):17-30, 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):2977-2987, 2018.

  • [GSWW20] D. Gabric, J. Sawada, A. Williams, and D. Wong. A successor rule framework for constructing $k$-ary de Bruijn sequences and universal cycles. IEEE Transactions on Information Theory, 66(1):679–687, 2020.

  • [Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011.

  • [NW22] A. Nellore and R. Ward. Arbitrary-Length Analogs to de Bruijn Sequences. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), volume 223, pages 9:1–9:20,2022.

  • [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.

  • [SSA20] E. Sala, J. Sawada, A. Alhakim. Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences. arXiv preprint arXiv:2010.07960, 2020.

  • [WWW18] X. Wang, D. Wong, and Z. WeiGuo. A simple greedy de Bruijn sequence construction. In Sequences and Their Applications (SETA 2018), 2018.

Interested in generating other combinatorial objects? Visit http://combos.org