my-thesis

Preliminares

• Teoría de lenguajes
• Autómatas
• Maquina de Turing
• Complejidad Computacional
• Problema de la satisfacibilidad booleana

Formalismos de escritura regulada

• Gramáticas Matriciales
• Gramáticas de Índice Global
• Gramáticas de Concatenación de Rango

Estrategia para la solución del SAT usando el problema del vacío

• Antecedentes
• Autómata booleano
• Problema de satisfacibilidad booleana libre del contexto
• Problema de satisfacibilidad booleana de concatenación de rango simple
• Transformación de una fórmula booleana en una cadena
• Primera aproximación del SAT usando gramáticas matriciales simples

Estrategia para la solución del SAT usando el problema del vacío

• Definición de $L_{S-SAT}$
• Transductor $T_{SAT}$
• $L_{S-SAT}$ como lenguaje de índice global

Estrategia para la solución del SAT usando el gramáticas de concatenación de rango

• $L_{0,1}$ como lenguaje de concatenación de rango
• Solución del SAT usando el problema del vacío
• Solución del SAT usando el problema de la palabra
• Clases de problemas que reconocen las RCG
• Instancias de SAT polinomiales empleando RCG