De Bruijn sequences and De Bruijn graphs for a general language

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.