De Bruijn sequences and De Bruijn graphs for a general language

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


A de Bruijn sequence over a finite alphabet of span n is a cyclic string such that all words of length n appear exactly once as factors of this sequence. We extend this definition to a subset of words of length n, characterizing for which subsets exists a de Bruijn sequence. We also study some symbolic dynamical properties of these subsets extending the definition to a language defined by forbidden factors. For these kinds of languages we present an algorithm to produce a de Bruijn sequence. In this work we use graph-theoretic and combinatorial concepts to prove these results.

Original languageEnglish
Pages (from-to)214-219
Number of pages6
JournalInformation Processing Letters
Issue number6
StatePublished - 31 Dec 2005


  • Combinatorial problems
  • Combinatorics on words
  • De Bruijn graphs
  • De Bruijn sequences
  • Eulerian labeled graphs
  • Graph algorithms


Dive into the research topics of 'De Bruijn sequences and De Bruijn graphs for a general language'. Together they form a unique fingerprint.

Cite this