Definición y solución de una nueva variante de búsquedas de cadenas llamada búsqueda δγ—Parametrizada

Esta tesis define un nuevo problema de búsqueda de cadenas que combina dos paradigmas: Búsqueda δγ y Búsqueda Parametrizada. La solución obtenida es una combinación de técnicas de paralelismo de bits y una reducción a un problema the matchings en grafos. La complejidad en tiempo del algoritmo es O(nm), asumiendo que el tamaño del texto es n, el tamaño de patrón es m y que el alfabeto es de tamaño constante. / Abstract. This thesis defines a new pattern matching problem by combining two paradigms: δγ–matching and parameterized matching. The solution is essentially obtained by a combination of bitparallel techniques and a reduction to a graph matching problem. The time complexity of the algorithm is O(nm), assuming text size n, pattern size m and a constant alphabet size.

• Autores: Mendivelso Moreno, Juan Carlos
• Fecha de publicación: 2010
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/70484
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/70484; http://bdigital.unal.edu.co/2759/
• Palabra clave: 0 Generalidades / Computer science, information and general works; 62 Ingeniería y operaciones afines / Engineering; Búsqueda de cadenas; Búsqueda δγ; Búsqueda parametrizada; Matching en grafos bipartitos; Paralelismo de bits; Pattern matching; δγ–matching; Parameterized matching; Bipartite matching; Bit-parallelism
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional