Reescritura
En matemáticas , ciencias de la computación y lógica , la reescritura cubre una amplia gama de métodos para reemplazar los términos de una fórmula por otros términos. Tales métodos pueden ser alcanzados por los sistemas de reescritura (también conocido 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, más 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 formas 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 a 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 coincida 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 tal sistema, cada regla se elige de modo que el lado izquierdo sea equivalente al lado derecho y, en consecuencia, cuando el lado izquierdo coincide con una subexpresión, realizar una reescritura de esa subexpresión de izquierda a derecha mantiene la coherencia lógica y el valor de toda la expresión. .
Se pueden emplear sistemas de reescritura de términos 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 simple es la utilizada en los axiomas de Peano , basado en la constante de 0 (cero) y la función sucesor 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 utilizar 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. Dicha regla generalmente toma la forma A → X, donde A es una etiqueta de categoría sintáctica , como un sintagma nominal u oración , y X es una secuencia de tales etiquetas o morfemas , expresando el hecho de que A puede ser reemplazado por X al generar el estructura constituyente de una oración. Por ejemplo, la regla S → NP VP significa que una oración puede constar de un sintagma nominal seguido de un sintagma verbal; más reglas especificarán en qué subconstituyentes pueden consistir un sintagma nominal y un sintagma verbal, y así sucesivamente.
