De Bruijn Sequences and Universal Cycles

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, permutations, fixed-content)
- 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.