An Efficient Shift Rule for the Prefer-Max De Bruijn Sequence Academic Article uri icon

abstract

  • A shift rule for the prefer-max De Bruijn sequence is formulated, for all sequence orders, and over any finite alphabet. An efficient algorithm for this shift rule is presented, which has linear (in the sequence order) time and memory complexity … Keywords: De Bruijn sequence, Ford sequence, prefer-max sequence, shift rule 2010 MSC: 94A55, 05C45, 05C38 … A k-ary De Bruijn sequence of order n (denoted (n, k)-DB), is a string 〈νi〉 kn−1 i=0 ν0ν1 ... νkn−1 over the alphabet [k] {0, 1, . . . , k − 1}, ie, νi ∈ [k] … ✩This work was supported in part by the …

publication date

  • January 1, 2017