Multi-Shift de Bruijn Sequence

Details Multi-Shift de Bruijn Sequence Multi-Shift de Bruijn Sequence

2010-04-08

arxiv.org/abs/1004.1216v1

Computer Science

Discrete Mathematics

9 pages

Scientific paper

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 a multi-shift setting: a multi-shift de Bruijn sequence tau(m,n) of shift m and order n is a word such that every word of length n appears exactly once in w as a factor that starts at index im+1 for some integer i>=0. We show the number of the multi-shift de Bruijn sequence tau(m,n) is (a^n)!a^{(m-n)(a^n-1)} for 1<=n<=m and is (a^m!)^{a^{n-m}} for 1<=m<=n, where a=|Sigma|. We provide two algorithms for generating a tau(m,n). The multi-shift de Bruijn sequence is important in solving the Frobenius problem in a free monoid.

Affiliated with

Also associated with

No associations

Rating

Multi-Shift de Bruijn Sequence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multi-Shift de Bruijn Sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-Shift de Bruijn Sequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-712864