reescritura

En matemáticas , ciencias de la computación y lógica , la reescritura cubre una amplia gama de métodos para reemplazar subtérminos de una fórmula con otros términos. Dichos métodos pueden lograrse mediante sistemas de reescritura (también conocidos como sistemas de reescritura , motores de reescritura , ^{[1] [2]} o sistemas de reducción ). En su forma más básica, consisten en un conjunto de objetos, además de relaciones sobre cómo transformar esos objetos.

La reescritura puede ser no determinista . Una regla para reescribir un término podría aplicarse de muchas maneras diferentes a ese término, o podría aplicarse más de una regla. Los sistemas de reescritura no proporcionan un algoritmo para cambiar un término por otro, sino un conjunto de posibles aplicaciones de reglas. Sin embargo, cuando se combinan con un algoritmo apropiado, los sistemas de reescritura pueden verse como programas de computadora , y varios probadores de teoremas ^[3] y lenguajes de programación declarativos se basan en la reescritura de términos. ^{[4] [5]}

En lógica , el procedimiento para obtener la forma normal conjuntiva (CNF) de una fórmula se puede implementar como un sistema de reescritura. ^[6] Las reglas de un ejemplo de tal sistema serían:

donde el símbolo ( ) indica que una expresión que coincide con el lado izquierdo de la regla se puede reescribir a una formada por el lado derecho, y cada uno de los símbolos denota una subexpresión. En un sistema de este tipo, cada regla se elige de manera que el lado izquierdo sea equivalente al lado derecho y, en consecuencia, cuando el lado izquierdo coincida con una subexpresión, la reescritura de esa subexpresión de izquierda a derecha mantiene la consistencia lógica y el valor de toda la expresión. .${\ estilo de visualización \ a }$

Los sistemas de reescritura de términos se pueden emplear para calcular operaciones aritméticas con números naturales . Con este fin, cada uno de esos números debe codificarse como un término . La codificación más sencilla es la utilizada en los axiomas de Peano , basada en la constante 0 (cero) y la función sucesora S. Por ejemplo, los números 0, 1, 2 y 3 están representados por los términos 0, S(0), S(S(0)) y S(S(S(0))), respectivamente. El siguiente término sistema de reescritura se puede usar para calcular la suma y el producto de números naturales dados. ^[7]

En lingüística , las reglas de estructura de frases , también llamadas reglas de reescritura , se utilizan en algunos sistemas de gramática generativa , ^[8] como un medio para generar las oraciones gramaticalmente correctas de un idioma. Tal regla típicamente toma la forma , donde A es una etiqueta de categoría sintáctica , como un sintagma nominal o una oración , y X es una secuencia de tales etiquetas o morfemas , expresando el hecho de que A puede ser reemplazada por X al generar la estructura constituyente de una sentencia. Por ejemplo, la regla significa que una oración puede consistir en una frase nominal (NP) seguida de una frase verbal${\displaystyle {\rm {A\rightarrow X}}}$${\displaystyle {\rm {S\rightarrow NP\VP}}}$(VP); otras reglas especificarán en qué subconstituyentes puede consistir un sintagma nominal y un sintagma verbal, y así sucesivamente.

Fig.1: Diagrama triangular esquemático de la aplicación de una regla de reescritura en la posición de un término, con sustitución coincidente${\displaystyle l\longrightarrow r}$${\ estilo de visualización p}$${\ estilo de visualización \ sigma}$

Fig.2: Regla lhs término coincidencia en término${\ estilo de visualización x * (y * z)}$${\displaystyle {\frac{a*((a+1)*(a+2))}{1*(2*3)}}}$