Un sistema formal formado por un conjunto de reglas de reescritura dirigidas que transforman términos en otros términos mediante reemplazos dirigidos por patrones y sustitución.

Principio

Reglas de la forma l -> r se aplican a ocurrencias de instancias de l en un término mayor mediante matching y sustitución; las aplicaciones repetidas generan secuencias de reducción cuyas propiedades (terminación, confluencia) determinan la existencia y unicidad de formas normales.

Demostración

Con reglas { f(a) -> b, f(x) -> g(x) } y término f(f(a)), se aplica primero f(a) -> b en la ocurrencia interna obteniendo f(b), y luego quizá f(x) -> g(x) produce g(b); distintos órdenes de aplicación pueden dar resultados distintos si el sistema no es confluyente.

Aplicación incorrecta

Esperar formas normales únicas o terminación de un TRS sin verificar confluencia o terminación; aplicar reglas sin tener en cuenta captura de variables o condiciones contextuales exigidas por el formato de la regla.

Consecuencia

Bien diseñado, un TRS proporciona normalización algorítmica, procedimientos de decisión para teorías ecuacionales y semánticas operacionales para lenguajes de programación y demostradores automáticos.

Inversión

Invertir la dirección tratando las reglas como ecuaciones bidireccionales (l ↔ r) para formar una teoría ecuacional; esto suprime la direccionalidad de la reducción y desplaza el foco de la computación a la razonamiento sobre igualdad.

Límite

Se aplica a términos de primer orden bajo una firma y conjunto de reglas dados; los TRS estándar excluyen construcciones de orden superior con enlace, operaciones con efectos secundarios o restricciones contextuales salvo que se extiendan explícitamente.

Tensión semántica

Tensión entre ver las reglas como pasos computacionales deterministas (reescritura) y verlas como igualdades lógicas (ecuaciones), donde la dirección y la estrategia son críticas en una visión y secundarias en la otra; ambas influyen en criterios de corrección.

Síntesis

Un Sistema de Reescritura de Términos es un mecanismo sintáctico compuesto por reglas de reemplazo dirigidas que, por matching y sustitución, ejecuta transformaciones de términos; su utilidad depende de propiedades meta como terminación y confluencia que controlan determinismo y decidibilidad.