Abstract
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 language | English |
|---|---|
| Pages (from-to) | 214-219 |
| Number of pages | 6 |
| Journal | Information Processing Letters |
| Volume | 96 |
| Issue number | 6 |
| DOIs | |
| State | Published - 31 Dec 2005 |
Keywords
- Combinatorial problems
- Combinatorics on words
- De Bruijn graphs
- De Bruijn sequences
- Eulerian labeled graphs
- Graph algorithms