Research problems
- Generalize the binary successor rules for the prefer-same and prefer-opposite sequences [SSA20] for $k$-ary alphabets. What is the underlying feedback function?
- Is there a simple to understand concatenation construction for the lexicographic composition construction [FK77] of de Bruijn sequences?
- Is there a generalization of the lexicographic composition construction [FK77] to $k$-ary alphabets?
- 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!
- Can cut-down DB sequences be generated in $O(1)$-amortized time using $O(n)$ space [CGS21,NW22]? Solved!
- Is there a simple successor rule for the greedy XNOR construction [WWW18]?
- Construct balanced cut-down DB sequences efficiently by finding a simple successor rule [NW22].
- What is the number of distinct balanced cut-down DB sequences for a given length $m$ and alphabet size $k$ [NW22]?
- 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!
- 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
- 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.
- Develop new and interesting applications that apply de Bruijn sequences and universal cycles.
- 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
- 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]?
- Generalize the notion of discrepancy for $k$-ary de Bruijn sequences.
- 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.