Tesis Doctorado
Secuencias y grafos de brujin en lenguajes con restricciónes.
Autor
Moreno-Araya, Eduardo Enrique
Institución
Resumen
Una secuencia de De Bruijn de extensión n es una palabra cíclica tal que todas las palabras de un largo fijo n aparecen exactamente una vez como factor de la secuencia. Fredricksen y Maiorana construyeron un algoritmo para generar la secuencia de De Bruijn lexicográficamente minimal, el cual utiliza las palabras de Lyndon. Esta tesis estudia cómo generalizar el concepto de secuencias de De Bruijn para un lenguaje compuesto de un subconjunto de palabras de largo n, particularmente los lenguajes de todas las palabras de largo n sin factores en una lista de factores prohibidos. Inicialmente, se estudia el caso de las palabras sin el factor 11. Se da una demostración del algoritmo de Fredricksen y Maiorana que permite extender este resultado al caso de las palabras sin el factor 1i para cualquier i. Luego se caracteriza para cuáles lenguajes de palabras de largo n existe una secuencia de De Bruijn y se estudia alguans propiedades de la dinámica simbólica de estos lenguajes, particularmente de los lenguajes definidos por factores prohibidos. Para este tipo de lenguajes, se presenta un algoritmo que produce una secuencia de De Bruijn usando las palabras de Lyndon del lenguaje. Este resultado usa la noción de un grafo de De Bruijn y reduce el problema a encontrar un ciclo Euleriano en este grafo. Por último, se estudia el problema de construir la secuencia de De Bruijn lexicográficamente minimal para un lenguaje con factores prohibidos usando el grafo de De Bruijn. Se estudia dos algoritmos, un algoritm glotón, simple y eficiente, que funciona para algunos conjuntos de lenguajes, y otro algoritmo más complejo que resuelve este problema apra cualquier grafo Euleriano etiquetado. PFCHA-Becas Doctor en Ciencias de la Ingeniería Mención Modelación Matemática 83p. PFCHA-Becas TERMINADA