Minimum de Bruijn Sequence in a Language with Forbidden Substrings

2007/11/12 by Eduardo Moreno, Moreno, Eduardo, Martin Matamala +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.0711.1695

arxiv created 2007/11/12 · arxiv updated 2009/12/01

Abstract

Let be the following strategy to construct a walk in a labeled digraph: at each vertex, we follow the unvisited arc of minimum label. In this work we study for which languages, applying the previous strategy over the corresponding de Bruijn graph, we finish with an Eulerian cycle, in order to obtain the minimal de Bruijn sequence of the language.

Related

• Minimal Eulerian trail in a labeled digraph
• An Unoriented Variation on de Bruijn Sequences
• A note on watchman's walks in de Bruijn graphs
• Extending de Bruijn sequences to larger alphabets
• De Bruijn Graph Homomorphisms and Recursive De Bruijn Sequences