Titulo:  Sobre la extensión de la secuencia de Bruijn lexicográficamente máxima  a alfabetos más grandes

Directora : Verónica Becher

Jurados: Sergio Abriola y Olivier Carton

Resumen. Una secuencia de Bruijn de orden n en k símbolos es una secuencia en la que cada palabra de longitud n ocurre exactamente una vez. Se sabe que para cada secuencia r de Bruijn v de orden n  en k símbolos hay otra secuencia  de Bruijn w de orden n pero en k+1 símbolos tal que v es una subsecuencia de w. En esta tesis nos dedicamos a la secuencia de Bruijn lexicográficamente máxima, a la que llamamos dual-Ford. El nombre se debe a que la secuencia de Bruijn lexicográficamente mínima es conocida como la secuencia de Ford.

Demostramos que la secuencia dual-Ford de un orden dado y un alfabeto dado es un sufijo de la secuencia dual-Ford del mismo orden en un alfabeto con un símbolo más. Dado que hay un algoritmo lineal en tiempo y espacio para generar las secuencias Ford y las duales-Ford, el resultado que presentamos aquí  determina un algoritmo lineal en tiempo y espacio para generar la extensión.