- Teoría de lenguajes
- Autómatas
- Maquina de Turing
- Complejidad Computacional
- Problema de la satisfacibilidad booleana
- Gramáticas Matriciales
- Gramáticas de Índice Global
- Gramáticas de Concatenación de Rango
- 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
- Definición de
$L_{S-SAT}$ - Transductor
$T_{SAT}$ -
$L_{S-SAT}$ como lenguaje de índice global
-
$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