Glosario IA
El diccionario completo de la Inteligencia Artificial
Sistema de reescritura
Conjunto formal de reglas de transformación que permiten modificar expresiones simbólicas según esquemas predefinidos. Constituye el fundamento matemático de numerosos mecanismos de cálculo y prueba automática.
Regla de reescritura
Par (l, r) donde l es el miembro izquierdo y r el miembro derecho, especificando cómo sustituir un patrón por otro en una expresión. La reescritura se aplica cuando el patrón l es identificado en el término a transformar.
Forma normal
Expresión que ya no puede ser reescrita por ninguna regla del sistema. El alcance de una forma normal garantiza la terminación del proceso de reescritura para ese término específico.
Confluencia
Propiedad que garantiza que diferentes caminos de reescritura a partir de un mismo término convergen hacia una forma normal única. Esencial para asegurar el determinismo de los cálculos y la coherencia de los resultados.
Terminación
Propiedad de un sistema de reescritura que garantiza que ninguna secuencia infinita de reescrituras es posible. Condición necesaria para la existencia de algoritmos de decisión y procedimientos de cálculo efectivos.
Reescritura de términos
Paradigma de cálculo donde las transformaciones se aplican a términos estructurados en árboles según reglas de sustitución. Fundamento de muchos lenguajes de programación funcionales y sistemas de prueba.
Sistema de Knuth-Bendix
Algoritmo de completación que transforma un sistema de reescritura no confluente en un sistema convergente equivalente. Utilizado para la resolución de ecuaciones y la demostración automática de teoremas.
Par crítico
Superposición no trivial entre dos reglas de reescritura que puede generar una no-confluencia. El análisis de los pares críticos permite detectar y resolver los conflictos en los sistemas de reescritura.
Orden de reducción
Relación de orden bien fundada sobre los términos utilizada para probar la terminación de un sistema de reescritura. Permite garantizar que cada reescritura disminuye estrictamente los términos según este orden.
Reescritura condicional
Extensión de los sistemas de reescritura donde la aplicación de una regla depende de la satisfacción de condiciones previas. Permite modelar transformaciones más complejas y contextuales.
Teorema de Church-Rosser
Resultado fundamental que establece la equivalencia entre confluencia y la existencia de una forma normal única. Base teórica que garantiza la coherencia de los sistemas de cálculo por reescritura.
Estrategia de reescritura
Política que determina el orden y la selección de las reescrituras a aplicar en un término. Influye en la eficiencia computacional y puede guiar hacia resultados específicos.
Reescritura de cadenas
Especialización de la reescritura donde los términos son cadenas de caracteres y las reglas son sustituciones contextuales. Fundamental en lingüística computacional y teoría de lenguajes formales.
Criterio de Newman
Teorema que establece que un sistema de reescritura terminante es confluente si y solo si todos sus pares críticos convergen. Simplifica la verificación de confluencia en los sistemas finitos.