DE BRUIJN SEQUENCES REVISITED
A (non-circular) de Bruijn sequence w of order n is a word such that every word of length n appears exactly once in w as a factor. In this paper, we generalize the concept to different settings: the multi-shift de Bruijn sequence and the pseudo de Bruijn sequence. An m-shift de Bruijn sequence of order n is a word such that every word of length n appears exactly once in w as a factor that starts at a position im + 1 for some integer i >= 0. A pseudo de Bruijn sequence of order n with respect to an antimorphic involution theta is a word such that for every word u of length n the total number of appearances of u and theta(u) as a factor is one. We show that the number of or-shift de Bruijn sequences of order n is a(n)!a((m-n)(an-1)) for 1 <= n <= m and is (a(m)!)(an-m) for 1 <= m <= n, where a is the size of the alphabet. We provide two algorithms for generating a multi-shift de Bruijn sequence. The multi-shift de Bruijn sequence is important for solving the Frobenius in a free monoid. We show that the existence of pseudo de Bruijn sequences depends on the given alphabet and antimorphic involution, and obtain formulas for the number of such sequences in some particular settings.
de bruijn sequence multi-shift de bruijn sequence pseudo de bruijn sequence antimorphic involution