Special Issue – Automata and Formal Languages (AFL 2011)No Access

DE BRUIJN SEQUENCES REVISITED

The University of Western Ontario, London, Ontario, Canada N6A 5B7, Canada

This research was partially supported by a Natural Sciences and Engineering Council of Canada Discovery Grant, and Canada Research Chair Award to L.K.

Search for more papers by this author

and

ZHI XU

The University of Western Ontario, London, Ontario, Canada N6A 5B7, Canada

Part of the work was done during this author's stay at University of Waterloo, supported by D. R. Cheriton Scholarship. This author's current address is Google Waterloo, 151 Charles St. W #200, Kitchener, Ontario, Canada N2G 1H6.

Search for more papers by this author

https://doi.org/10.1142/S0129054112400540Cited by:3 (Source: Crossref)

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 aⁿ!a^{(m-n)(aⁿ-1)} for 1 ≤ n ≤ m and is (a^m!)^{a^n-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:

Remember to check out the Most Cited Articles!
Check out these Handbooks in Computer Science

References

T. van Aardenne-Ehrenfest and N. G. de Bruijn, Simon Stevin 28, 203 (1951). Google Scholar
N. G. de Bruijn, Indag. Math. 8(4), 461 (1946). Google Scholar
E. Chiniforooshan, L. Kari and Z. Xu, Fundamenta Informaticae 114, 1 (2012). Web of Science, Google Scholar
E. Czeizler, L. Kari and S. Seki, Theoret. Comput. Sci. 411(3), 617 (2010), DOI: 10.1016/j.tcs.2009.09.037. Crossref, Web of Science, Google Scholar
A. de Luca and A. De Luca, Theoret. Comput. Sci. 362, 282 (2006). Crossref, Web of Science, Google Scholar
C. Flye Sainte-Marie, L'Intermédiaire Math. 1, 107 (1894). Web of Science, Google Scholar
H. Fredricksen, SIAM Review 24(2), 195 (1982), DOI: 10.1137/1024041. Crossref, Web of Science, Google Scholar
H. Fredricksen and I. J. Kessler, J. Combin. Theory Ser. A 22, 17 (1977), DOI: 10.1016/0097-3165(77)90059-0. Crossref, Web of Science, Google Scholar
S. W. Golomb , Shift Register Sequences ( Holden-Day , 1967 ) . Google Scholar
I. J. Good, J. London Math. Soc. 21(3), 167 (1946). Web of Science, Google Scholar
J.-Y. Kao, J. Shallit and Z. Xu, The Frobenius problem in a free monoid, STACS 2008 (2008) pp. 421–432. Google Scholar
L. Kari and K. Mahalingam, Watson-Crick conjugate and commutative words, Proceedings of DNA134848, LNCS (2008) pp. 273–283. Google Scholar
L. Kari and S. Seki, J. Comput. System Sci. 75(2), 113 (2009), DOI: 10.1016/j.jcss.2008.08.002. Crossref, Web of Science, Google Scholar
G. Kirchhoff, Ann. Phys. Chem. 72, 497 (1847). Google Scholar
D. E. Knuth , The Art of Computer Programming ( Addison-Wesley , 1969 ) . Google Scholar
M. H. Martin, Bull. Amer. Math. Soc. 40, 859 (1934), DOI: 10.1090/S0002-9904-1934-05988-3. Crossref, Google Scholar
A. Ralston. De Bruijn sequences — a model example of the interaction of discrete mathematics and computer science. Math. Mag., 55(3):131–143, 1982 . Google Scholar
D. Rees, J. London Math. Soc. 21(3), 169 (1946). Google Scholar
W. T. Tutte and C. A. B. Smith, Amer. Math. Monthly 48(4), 233 (1941), DOI: 10.2307/2302716. Crossref, Google Scholar