Minimal de Bruijn sequence in a language with forbidden substrings

DOI10.1007/978-3-540-30559-0_14MaRDI QIDQ5710797zbMATH OpenOpenAlexFDO

Authors Eduardo Moreno, Martin Matamala

Publication date 8 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.1695

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorics on words (68R15)

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.

Recommendations

• Minimum Eulerian circuits and minimum de Bruijn sequences
• Minimal Eulerian Circuit in a Labeled Digraph
• de Bruijn sequences and de Bruijn graphs for a general language
• An unoriented variation on de Bruijn sequences
• Minimal forbidden subwords

Cited in

(4)

• Minimum Eulerian circuits and minimum de Bruijn sequences
• Designing preference functions for de Bruijn sequences with forbidden words
• Minimal Eulerian Circuit in a Labeled Digraph
• The lexicographically smallest universal cycle for binary strings with minimum specified weight

This page was built for publication: Minimal de Bruijn sequence in a language with forbidden substrings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5710797)