ICC 25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
Extending de Bruijn sequences to larger alphabets
Autor/es:
BECHER, VERÓNICA; CORTÉS, LUCAS
Revista:
INFORMATION PROCESSING LETTERS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2021 vol. 168
ISSN:
0020-0190
Resumen:
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.
