DE BRUIJN SEQUENCES REVISITED
Authors:
- 1 September 2012
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 23 (06) , 1307-1321
Abstract
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 θ is a word such that for every word u of length n the total number of appearances of u and θ(u) as a factor is one. We show that the number of m-shift de Bruijn sequences of order n is an!a(m-n)(an-1) for 1 ≤ n ≤ m and is (am!)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 problem 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.Keywords
This publication has 7 references indexed in Scilit:
- On a special class of primitive wordsTheoretical Computer Science, 2010
- On pseudoknot-bordered words and their propertiesJournal of Computer and System Sciences, 2009
- Pseudopalindrome closure operators in free monoidsTheoretical Computer Science, 2006
- A Survey of Full Length Nonlinear Shift Register Cycle AlgorithmsSIAM Review, 1982
- Lexicographic compositions and deBruijn sequencesJournal of Combinatorial Theory, Series A, 1977
- On Unicursal Paths in a Network of Degree 4The American Mathematical Monthly, 1941
- A problem in arrangementsBulletin of the American Mathematical Society, 1934