Extending de Bruijn sequences to larger alphabets

DOI10.1016/J.IPL.2020.106085arXiv1907.00056MaRDI QIDQ6321238

Publication date: 28 June 2019

Abstract: A de Bruijn sequence of order n over a k-symbol alphabet is a circular sequence where each length-n sequence occurs exactly once. We present a way of extending de Bruijn sequences by adding a new symbol to the alphabet: the extension is performed by embedding a given de Bruijn sequence into another one of the same order, but over the alphabet with one more symbol, while ensuring that there are no long runs without the new symbol. Our solution is based on auxiliary graphs derived from the de Bruijn graph and solving a problem of maximum flow.

Mathematics Subject Classification ID

Combinatorics on words (68R15) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Flows in graphs (05C21)

This page was built for publication: Extending de Bruijn sequences to larger alphabets

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