De Bruijn Sequence and Universal Cycle Constructions
Research problems
- Generalize the binary shift rules for the prefer-same and prefer-opposite sequences [SSA20] for $k$-ary alphabets. What is the underlying feedback function?
- Is there a generalization of the lexicographic composition construction [FK77] to $k$-ary alphabets?
- Is there a concatenation construction for the simple PCR-based shift rules PCR3 and PCR4 [GSWW18,GSWW20]? If so, state as simply as possible. What is the underlying ordering of necklaces, and can they be efficiently generated?
- Efficiently construct balanced cut-down de Bruijn sequences by finding a simple shift rule [CGS21,NW21].
- Provide a simple and efficient shift-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?
- Decoding. This website highlights many interesting de Bruijn sequence constructions. However, only the 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
- Provide an implementation of the recursively generated de Bruijn sequences in [Knu11] along with corresponding decoding routines -- see Question 99 on P317 and the related answers on P699.
- Develop new and interesting applications that apply de Bruijn sequences and universal cycles.
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.
- [NW21] A. Nellore and R. Ward. Arbitrary-length analogs to de Bruijn sequences, arXiv:2108.07759, 2021.
- [SSA20] E. Sala, J. Sawada, A. Alhakim. Efficiently constructing the Prefer same de Bruijn sequence. Submitted 2020.