Repetitions in partial words

Identifier:  TDX:579

Handle: https://hdl.handle.net/20.500.11797/TDX579

Authors:  Mercas, Robert

Abstract:
El objeto de esta tesis está representado por las repeticiones de palabras parciales, palabras que, además de las letras regulares, pueden tener un número de símbolos desconocidos,llamados símbolos 'agujeros' o 'no sé qué'. Más concretamente, se presenta y se resuelve una extensión de la noción de repetición establecida por Axel Thue. Investigamos las palabras parciales con un número infinito de agujeros que cumplen estas propiedades y, también las palabras parciales que conservan las propiedades después de la inserción de un número arbitrario de agujeros, posiblemente infinito. Luego, hacemos un recuento del número máximo de 2-repeticiones distintas compatibles con los factores de una palabra parcial. Se demuestra que el problema en el caso general es difícil, y estudiamos el problema en el caso de un agujero. Al final, se estudian algunas propiedades de las palabras parciales sin fronteras y primitivas (palabras sin repeticiones) y se da una caracterización del lenguaje de palabras parciales con una factorización crítica.