Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777040 | Discrete Mathematics | 2017 | 8 Pages |
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).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Joe Sawada, Aaron Williams, Dennis Wong,