Abstract
A k-ary de Bruijn sequence of order n is a cyclic sequence of length kn in which each k-ary string of length n appears exactly once as a substring. A shift rule for a de Bruijn sequence of order n is a function that maps each length n substring to the next length n substring in the sequence. We present the first known shift rule for k-ary de Bruijn sequences that runs in O(1)-amortized time per symbol using O(n) space. Our rule generalizes the authors’ recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127–131).
Original language | English |
---|---|
Pages (from-to) | 524-531 |
Number of pages | 8 |
Journal | Discrete Mathematics |
Volume | 340 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Mar 2017 |
Externally published | Yes |
Keywords
- CAT algorithm
- De Bruijn sequence
- Generate
- Necklaces
- Shift Gray code
- Shift rule
- Successor rule
- Universal cycle
- k-ary de Bruijn sequence