Reescritura

Reemplazar subtérmino en una fórmula con otro término

En matemáticas , informática 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, constan de 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 ser aplicable más de una regla. Los sistemas de reescritura entonces 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 demostradores de teoremas ^[3] y lenguajes de programación declarativos se basan en la reescritura de términos. ^{[4] [5]}

Casos de ejemplo

Lógica

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

${\displaystyle \neg \neg A\to A}$( eliminación de doble negación )

${\displaystyle \neg (A\land B)\to \neg A\lor \neg B}$( Leyes de De Morgan )

${\displaystyle \neg (A\lor B)\to \neg A\land \neg B}$

${\displaystyle (A\land B)\lor C\to (A\lor C)\land (B\lor C)}$( distributividad )

${\displaystyle A\lor (B\land C)\to (A\lor B)\land (A\lor C),}$^{[nota 1]}

donde el símbolo ( ) indica que una expresión que coincida con el lado izquierdo de la regla se puede reescribir en una formada por el lado derecho, y cada símbolo denota una subexpresión. En dicho 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. . ${\displaystyle \to }$

Aritmética

Se pueden emplear sistemas de reescritura de términos para calcular operaciones aritméticas con números naturales . Para ello, cada uno de estos 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 sistema de reescritura de términos se puede utilizar para calcular la suma y el producto de números naturales dados. ^[7]

${\displaystyle {\begin{aligned}A+0&\to A&{\textrm {(1)}},\\A+S(B)&\to S(A+B)&{\textrm {(2)}},\\A\cdot 0&\to 0&{\textrm {(3)}},\\A\cdot S(B)&\to A+(A\cdot B)&{\textrm {(4)}}.\end{aligned}}}$

Por ejemplo, el cálculo de 2+2 para dar como resultado 4 se puede duplicar reescribiendo el término de la siguiente manera:

${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(\;S(S(0))+S(0)\;)}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(S(\;S(S(0))+0\;))}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

donde los números de las reglas se dan encima de la flecha de reescritura .

Como otro ejemplo, el cálculo de 2⋅2 se ve así:

${\displaystyle S(S(0))\cdot S(S(0))}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))\cdot S(0)}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+S(S(0))\cdot 0}$ ${\displaystyle \;\;{\stackrel {(3)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+0}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {\textrm {s.a.}}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

donde el último paso comprende el cálculo del ejemplo anterior.

Lingüística

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 normalmente toma la forma donde A es una etiqueta de categoría sintáctica , como frase u oración nominal , y X es una secuencia de tales etiquetas o morfemas , expresando el hecho de que A puede ser reemplazado por X al generar la estructura constituyente de una sentencia. Por ejemplo, la regla significa que una oración puede consistir en un sintagma nominal (NP) seguido de un sintagma verbal (VP); reglas adicionales especificarán en qué subconstituyentes puede consistir un sintagma nominal y un sintagma verbal, y así sucesivamente. ${\displaystyle {\rm {A\rightarrow X}}}$ ${\displaystyle {\rm {S\rightarrow NP\ VP}}}$

Sistemas de reescritura abstracta

De los ejemplos anteriores, queda claro que podemos pensar en reescribir sistemas de manera abstracta. Necesitamos especificar un conjunto de objetos y las reglas que se pueden aplicar para transformarlos. El escenario más general (unidimensional) de esta noción se denomina sistema de reducción abstracto ^[9] o sistema de reescritura abstracta (abreviado ARS ). ^[10] Un ARS es simplemente un conjunto A de objetos, junto con una relación binaria → en A llamada relación de reducción , relación de reescritura ^[11] o simplemente reducción . ^[9]

Se pueden definir muchas nociones y notaciones en el entorno general de una ARS. es la clausura transitiva reflexiva de . es el cierre simétrico de . es el cierre simétrico transitivo reflexivo de . El problema planteado para una ARS es determinar, dados x e y , si . Un objeto x en A se llama reducible si existe algún otro y en A tal que ; de lo contrario se llama irreductible o forma normal . Un objeto y se llama "forma normal de x " si , y y es irreducible. Si la forma normal de x es única, generalmente se denota con . Si cada objeto tiene al menos una forma normal, la ARS se llama normalización . o se dice que x e y se pueden unir si existe alguna z con la propiedad de que . Se dice que una ARS posee la propiedad de Church-Rosser si implica . Una ARS es confluente si para todo w , x e y en A , implica . Una ARS es localmente confluente si y sólo si para todo w , x e y en A , implica . Se dice que una ARS es terminante o noetheriana si no existe una cadena infinita . Una ARS confluente y terminal se llama convergente o canónica . ${\displaystyle {\overset {*}{\rightarrow }}}$ ${\displaystyle \rightarrow }$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \rightarrow }$ ${\displaystyle {\overset {*}{\leftrightarrow }}}$ ${\displaystyle \rightarrow }$ ${\displaystyle x{\overset {*}{\leftrightarrow }}y}$ ${\displaystyle x\rightarrow y}$ ${\displaystyle x{\stackrel {*}{\rightarrow }}y}$ ${\displaystyle x{\downarrow }}$ ${\displaystyle x\downarrow y}$ ${\displaystyle x{\overset {*}{\rightarrow }}z{\overset {*}{\leftarrow }}y}$ ${\displaystyle x{\overset {*}{\leftrightarrow }}y}$ ${\displaystyle x\downarrow y}$ ${\displaystyle x{\overset {*}{\leftarrow }}w{\overset {*}{\rightarrow }}y}$ ${\displaystyle x\downarrow y}$ ${\displaystyle x\leftarrow w\rightarrow y}$ ${\displaystyle x{\mathbin {\downarrow }}y}$ ${\displaystyle x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots }$

Teoremas importantes para los sistemas de reescritura abstracta son que una ARS es confluente si tiene la propiedad de Church-Rosser, el lema de Newman (una ARS terminal es confluente si y sólo si es confluente localmente) y que el problema verbal para una ARS es indecidible en general.

Sistemas de reescritura de cadenas

Un sistema de reescritura de cadenas (SRS), también conocido como sistema semi-Thue , explota la estructura monoide libre de las cadenas (palabras) sobre un alfabeto para extender una relación de reescritura, a todas las cadenas del alfabeto que contienen izquierda y derecha, respectivamente. -lados laterales de algunas reglas como subcadenas . Formalmente, un sistema semi-Thue es una tupla donde hay un alfabeto (generalmente finito) y es una relación binaria entre algunas cadenas (fijas) del alfabeto, denominada conjunto de reglas de reescritura . La relación de reescritura de un paso inducida por on se define como: si hay cadenas, entonces si existen tales que , y . Dado que es una relación , el par se ajusta a la definición de un sistema de reescritura abstracta. Dado que la cadena vacía está en , es un subconjunto de . Si la relación es simétrica , entonces el sistema se llama sistema Thue . ${\displaystyle R}$ ${\displaystyle (\Sigma ,R)}$ ${\displaystyle \Sigma }$ ${\displaystyle R}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle s,t\in \Sigma ^{*}}$ ${\displaystyle s{\underset {R}{\rightarrow }}t}$ ${\displaystyle x,y,u,v\in \Sigma ^{*}}$ ${\displaystyle s=xuy}$ ${\displaystyle t=xvy}$ ${\displaystyle uRv}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle (\Sigma ^{*},{\underset {R}{\rightarrow }})}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle R}$

En un SRS, la relación de reducción es compatible con la operación monoide, lo que significa que implica para todas las cadenas . De manera similar, el cierre simétrico transitivo reflexivo de , denotado , es una congruencia , lo que significa que es una relación de equivalencia (por definición) y también es compatible con la concatenación de cadenas. La relación se llama congruencia de Thue generada por . En un sistema Thue, es decir, si es simétrico, la relación de reescritura coincide con la congruencia de Thue . ${\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}}$ ${\displaystyle x{\overset {*}{\underset {R}{\rightarrow }}}y}$ ${\displaystyle uxv{\overset {*}{\underset {R}{\rightarrow }}}uyv}$ ${\displaystyle x,y,u,v\in \Sigma ^{*}}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$

La noción de sistema semi-Thue coincide esencialmente con la presentación de un monoide . Como es una congruencia, podemos definir el factor monoide del monoide libre mediante la congruencia de Thue. Si un monoide es isomorfo con , entonces el sistema semi-Thue se denomina presentación monoide de . ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle {\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}_{R}}$ ${\displaystyle (\Sigma ,R)}$ ${\displaystyle {\mathcal {M}}}$

Inmediatamente obtenemos algunas conexiones muy útiles con otras áreas del álgebra. Por ejemplo, el alfabeto con las reglas , donde está la cadena vacía , es una presentación del grupo libre en un generador. Si por el contrario las reglas son justas , entonces obtenemos una presentación del monoide bicíclico . Por tanto, los sistemas semi-Thue constituyen un marco natural para resolver el problema verbal de monoides y grupos. De hecho, cada monoide tiene una presentación de la forma , es decir, siempre puede presentarse mediante un sistema semi-Thue, posiblemente sobre un alfabeto infinito. ${\displaystyle \{a,b\}}$ ${\displaystyle \{ab\rightarrow \varepsilon ,ba\rightarrow \varepsilon \}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \{ab\rightarrow \varepsilon \}}$ ${\displaystyle (\Sigma ,R)}$

El problema planteado para un sistema semi-Thue es indecidible en general; este resultado se conoce a veces como teorema de Post-Markov . ^[12]

Sistemas de reescritura de términos

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

Imagen 2: Regla izquierda que coincide con el término ${\displaystyle x*(y*z)}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$

Un sistema de reescritura de términos ( TRS ) es un sistema de reescritura cuyos objetos son términos , que son expresiones con subexpresiones anidadas. Por ejemplo, el sistema que se muestra en el § Lógica anterior es un sistema de reescritura de términos. Los términos de este sistema se componen de operadores binarios yy el operador unario . También están presentes en las reglas las variables, que representan cualquier término posible (aunque una sola variable siempre representa el mismo término en una sola regla). ${\displaystyle (\vee )}$ ${\displaystyle (\wedge )}$ ${\displaystyle (\neg )}$

A diferencia de los sistemas de reescritura de cadenas, cuyos objetos son secuencias de símbolos, los objetos de un sistema de reescritura de términos forman un álgebra de términos . Un término puede visualizarse como un árbol de símbolos, estando fijado el conjunto de símbolos admitidos por una firma determinada . Como formalismo, los sistemas de reescritura de términos tienen todo el poder de las máquinas de Turing , es decir, cada función computable puede definirse mediante un sistema de reescritura de términos. ^[13]

Definicion formal

Una regla de reescritura es un par de términos , comúnmente escritos como , para indicar que el lado izquierdo l puede ser reemplazado por el lado derecho r . Un sistema de reescritura de términos es un conjunto R de dichas reglas. Se puede aplicar una regla a un término s si el término izquierdo l coincide con algún subtérmino de s , es decir, si hay alguna sustitución tal que el subtérmino de con raíz en alguna posición p sea el resultado de aplicar la sustitución al término l . El subtérmino que coincide con el lado izquierdo de la regla se llama expresión redex o reducible . ^[14] El término resultante t de esta aplicación de regla es entonces el resultado de reemplazar el subtérmino en la posición p en s por el término con la sustitución aplicada, ver imagen 1. En este caso, se dice que se reescribe en un solo paso , o reescrito directamente , por el sistema , formalmente denotado como ,, o como por algunos autores. ${\displaystyle l\rightarrow r}$ ${\displaystyle l\rightarrow r}$ ${\displaystyle \sigma }$ ${\displaystyle s}$ ${\displaystyle \sigma }$ ${\displaystyle r}$ ${\displaystyle \sigma }$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle R}$ ${\displaystyle s\rightarrow _{R}t}$ ${\displaystyle s{\underset {R}{\rightarrow }}t}$ ${\displaystyle s{\overset {R}{\rightarrow }}t}$

Si un término se puede reescribir en varios pasos en un término , es decir, si , se dice que el término se reescribe en , formalmente denotado como . En otras palabras, la relación es el cierre transitivo de la relación ; A menudo, también se utiliza la notación para denotar la clausura reflexiva-transitiva de , es decir, si o . ^[15] Una reescritura de términos dada por un conjunto de reglas puede verse como un sistema de reescritura abstracto como se define anteriormente, con términos como sus objetos y como su relación de reescritura. ${\displaystyle t_{1}}$ ${\displaystyle t_{n}}$ ${\displaystyle t_{1}{\underset {R}{\rightarrow }}t_{2}{\underset {R}{\rightarrow }}\cdots {\underset {R}{\rightarrow }}t_{n}}$ ${\displaystyle t_{1}}$ ${\displaystyle t_{n}}$ ${\displaystyle t_{1}{\overset {+}{\underset {R}{\rightarrow }}}t_{n}}$ ${\displaystyle {\overset {+}{\underset {R}{\rightarrow }}}}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}}$ ${\displaystyle {\underset {R}{\rightarrow }}}$ ${\displaystyle s{\overset {*}{\underset {R}{\rightarrow }}}t}$ ${\displaystyle s=t}$ ${\displaystyle s{\overset {+}{\underset {R}{\rightarrow }}}t}$ ${\displaystyle R}$ ${\displaystyle {\underset {R}{\rightarrow }}}$

Por ejemplo, es una regla de reescritura, comúnmente utilizada para establecer una forma normal con respecto a la asociatividad de . Esa regla se puede aplicar en el numerador del término con la sustitución coincidente , ver imagen 2. ^{[nota 2]} Al aplicar esa sustitución al lado derecho de la regla se obtiene el término , y al reemplazar el numerador por ese término se obtiene , que es el Término resultante de aplicar la regla de reescritura. En conjunto, la aplicación de la regla de reescritura ha logrado lo que se llama "aplicar la ley de asociatividad para a " en álgebra elemental. Alternativamente, la regla podría haberse aplicado al denominador del término original, obteniendo . ${\displaystyle x*(y*z)\rightarrow (x*y)*z}$ ${\displaystyle *}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$ ${\displaystyle \{x\mapsto a,\;y\mapsto a+1,\;z\mapsto a+2\}}$ ${\displaystyle (a*(a+1))*(a+2)}$ ${\displaystyle {\frac {(a*(a+1))*(a+2)}{1*(2*3)}}}$ ${\displaystyle *}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}}$ ${\displaystyle {\frac {a*((a+1)*(a+2))}{(1*2)*3}}}$

Terminación

Los problemas de terminación de los sistemas de reescritura en general se tratan en Sistema de reescritura abstracta#Terminación y convergencia . En particular, para los sistemas de reescritura de términos, se deben considerar las siguientes sutilezas adicionales.

La terminación incluso de un sistema que consta de una regla con un lado izquierdo lineal es indecidible. ^{[16] [17]} La ​​terminación también es indecidible para sistemas que utilizan sólo símbolos de función unaria; sin embargo, es decidible para sistemas terrestres finitos . ^[18]

El siguiente término sistema de reescritura es normalizador, ^{[nota 3]} pero no terminante, ^{[nota 4]} y no confluente: ^[19]

$${\displaystyle {\begin{aligned}f(x,x)&\rightarrow g(x),\\f(x,g(x))&\rightarrow b,\\h(c,x)&\rightarrow f(h(x,c),h(x,x)).\\\end{aligned}}}$$

Los siguientes dos ejemplos de sistemas de reescritura de términos terminantes se deben a Toyama: ^[20]

${\displaystyle f(0,1,x)\rightarrow f(x,x,x)}$

y

${\displaystyle g(x,y)\rightarrow x,}$

${\displaystyle g(x,y)\rightarrow y.}$

Su unión es un sistema inextinguible, ya que

$${\displaystyle {\begin{aligned}&f(g(0,1),g(0,1),g(0,1))\\\rightarrow &f(0,g(0,1),g(0,1))\\\rightarrow &f(0,1,g(0,1))\\\rightarrow &f(g(0,1),g(0,1),g(0,1))\\\rightarrow &\cdots \end{aligned}}}$$

Dershowitz^[21]linealessuperposiciones ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$

Consulte Orden de reescritura y Orden de ruta (reescritura de términos) para conocer las relaciones de orden utilizadas en pruebas de terminación para sistemas de reescritura de términos.

Sistemas de reescritura de orden superior

Los sistemas de reescritura de orden superior son una generalización de los sistemas de reescritura de términos de primer orden a términos lambda , lo que permite funciones de orden superior y variables ligadas. ^[22] También se pueden reformular varios resultados sobre los TRS de primer orden para los HRS. ^[23]

Sistemas de reescritura de gráficos.

Los sistemas de reescritura de gráficos son otra generalización de los sistemas de reescritura de términos, que operan en gráficos en lugar de términos ( base ) / su correspondiente representación de árbol .

Sistemas de reescritura de trazas

La teoría de trazas proporciona un medio para discutir el multiprocesamiento en términos más formales, como a través del monoide de traza y el monoide de historia . La reescritura también se puede realizar en sistemas de seguimiento.

Ver también

• Par crítico (lógica)
• Compilador
• Algoritmo de finalización de Knuth-Bendix
• Los sistemas L especifican la reescritura que se realiza en paralelo.
• Transparencia referencial en informática.
• Reescritura regulada
• cálculo rho
• Redes de interacción

Notas

1. Esta variante de la regla anterior es necesaria ya que la ley conmutativa A ∨ B = B ∨ A no se puede convertir en una regla de reescritura. Una regla como A ∨ B → B ∨ A haría que el sistema de reescritura no fuera terminante.
2. ya que al aplicar esa sustitución al lado izquierdo de la regla se obtiene el numerador ${\displaystyle x*(y*z)}$ ${\displaystyle a*((a+1)*(a+2))}$
3. es decir, para cada término, existe alguna forma normal, por ejemplo, h ( c , c ) tiene las formas normales b y g ( b ), ya que h ( c , c ) → f ( h ( c , c ), h ( c , c )) → f ( h ( c , c ), f ( h ( c , c ), h ( c , c ))) → f ( h ( c , c ), g ( h ( c , c ))) → b , y h ( c , c ) → f ( h ( c , c ), h ( c , c )) → g ( h ( c , c )) → ... → g ( b ); ni b ni g ( b ) pueden reescribirse más, por lo tanto el sistema no es confluente
4. es decir, hay infinitas derivaciones, por ejemplo, h ( c , c ) → f ( h ( c , c ), h ( c , c )) → f ( f ( h ( c , c ), h ( c , c ) ) , h ( c , c )) → f ( f ( f ( h ( c , c ), h ( c , c ) ), h ( c , c )) , h ( c , c )) → ...

Otras lecturas

• Baader, Franz ; Nipkow, Tobías (1999). Reescritura de términos y todo eso . Prensa de la Universidad de Cambridge. ISBN 978-0-521-77920-3.316 páginas.
• Marc Bezem, Jan Willem Klop , Roel de Vrijer ("Terese"), Sistemas de reescritura de términos ("TeReSe"), Cambridge University Press, 2003, ISBN 0-521-39115-6 . Esta es la monografía completa más reciente. Sin embargo, utiliza una gran cantidad de notaciones y definiciones aún no estándar. Por ejemplo, la propiedad de Church-Rosser se define como idéntica a la confluencia. 
• Nachum Dershowitz y Jean-Pierre Jouannaud "Rewrite Systems", capítulo 6 en Jan van Leeuwen (Ed.), Manual de informática teórica, volumen B: modelos formales y semántica. , Elsevier y MIT Press, 1990, ISBN 0-444-88074-7 , págs. La preimpresión de este capítulo está disponible gratuitamente a través de los autores, pero le faltan las figuras. 
• Nachum Dershowitz y David Plaisted . "Reescritura", Capítulo 9 en John Alan Robinson y Andrei Voronkov (Eds.), Handbook of Automated Reasoning , Volumen 1 .
• Gérard Huet et Derek Oppen, Equations and Rewrite Rules, A Survey (1980) Stanford Verification Group, Informe N° 15 Informe del Departamento de Ciencias de la Computación N° STAN-CS-80-785
• Jan Willem Klop . "Term Rewriting Systems", Capítulo 1 en Samson Abramsky , Dov M. Gabbay y Tom Maibaum (Eds.), Handbook of Logic in Computer Science, Volumen 2: Antecedentes: Estructuras computacionales .
• David Plaisted. "Razonamiento ecuacional y sistemas de reescritura de términos", en Dov M. Gabbay , CJ Hogger y John Alan Robinson (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Volumen 1 .
• Jürgen Avenhaus y Klaus Madlener. "Reescritura de términos y razonamiento ecuacional". En Ranan B. Banerji (Ed.), Técnicas formales en inteligencia artificial: un libro de consulta , Elsevier (1990).

Reescritura de cadenas

• Ronald V. Book y Friedrich Otto, Sistemas de reescritura de cuerdas , Springer (1993).
• Benjamin Benninghofen, Susanne Kemmerich y Michael M. Richter , Sistemas de reducciones . LNCS 277 , Springer-Verlag (1987).

Otro

• Martin Davis , Ron Sigal, Elaine J. Weyuker , (1994) Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica - 2.ª edición , Academic Press, ISBN 0-12-206382-1 . 

enlaces externos

• La página de inicio de reescritura
• Grupo de Trabajo IFIP 1.6
• Investigadores en reescritura por Aart Middeldorp, Universidad de Innsbruck
• Portal de terminación
• Maude System: una implementación de software de un sistema de reescritura de términos genéricos. ^[5]

Referencias

1. Joseph Goguen Conferencia internacional "Probar y reescribir" sobre programación algebraica y lógica, 1990 Nancy, Francia, págs. 1-24
2. Sculthorpe, Neil; Frisby, Nicolás; Gill, Andy (2014). "El motor de reescritura de la Universidad de Kansas" (PDF) . Revista de programación funcional . 24 (4): 434–473. doi :10.1017/S0956796814000185. ISSN  0956-7968. S2CID  16807490. Archivado (PDF) desde el original el 22 de septiembre de 2017 . Consultado el 12 de febrero de 2019 .
3. Hsiang, Jieh; Kirchner, Hélène; Lescanne, Pierre; Rusinowitch, Michael (1992). "El enfoque de reescritura de términos para la demostración automatizada de teoremas". La revista de programación lógica . 14 (1–2): 71–99. doi : 10.1016/0743-1066(92)90047-7 .
4. Frühwirth, Thom (1998). "Teoría y práctica de las reglas de manejo de restricciones". La revista de programación lógica . 37 (1–3): 95–138. doi : 10.1016/S0743-1066(98)10005-5 .
5. Clavel, M.; Durán, F.; Eker, S.; Lincoln, P.; Martí-Oliet, N.; Meseguer, J.; Quesada, JF (2002). "Maude: Especificación y programación en lógica de reescritura". Informática Teórica . 285 (2): 187–243. doi : 10.1016/S0304-3975(01)00359-0 .
6. Kim Marriott; Peter J. Stuckey (1998). Programación con restricciones: una introducción. Prensa del MIT. págs. 436–. ISBN 978-0-262-13341-8.
7. Jürgen Avenhaus; Klaus Madlener (1990). "Reescritura de términos y razonamiento ecuacional". En RB Banerji (ed.). Técnicas Formales en Inteligencia Artificial . Libro de consulta. Elsevier. págs. 1–43.Aquí: Ejemplo en la sección 4.1, p.24.
8. Robert Freidin (1992). Fundamentos de la sintaxis generativa. Prensa del MIT. ISBN 978-0-262-06144-5.
9. Libro y Otto, p. 10
10. Bezem y otros, pág. 7,
11. Bezem y otros, pág. 7
12. Martín Davis y otros. 1994, pág. 178
13. Dershowitz, Jouannaud (1990), sección 1, p.245
14. Klop, JW "Sistemas de reescritura de términos" (PDF) . Artículos de Nachum Dershowitz y estudiantes . Universidad de Tel Aviv. pag. 12. Archivado (PDF) desde el original el 15 de agosto de 2021 . Consultado el 14 de agosto de 2021 .
15. N. Dershowitz, J.-P. Jouannaud (1990). Jan van Leeuwen (ed.). Reescribir sistemas . Manual de informática teórica. vol. B. Elsevier. págs. 243–320.; aquí: Secc. 2.3
16. Max Dauchet (1989). "Simulación de máquinas de Turing mediante una regla de reescritura lineal izquierda". Proc. 3° Int. Conf. sobre Técnicas y Aplicaciones de Reescritura . LNCS. vol. 355. Saltador. págs. 109-120.
17. Max Dauchet (septiembre de 1992). "Simulación de máquinas de Turing mediante una regla de reescritura regular". Informática Teórica . 103 (2): 409–420. doi : 10.1016/0304-3975(92)90022-8 .
18. Gerard Huet, DS Lankford (marzo de 1978). Sobre el problema de la detención uniforme de los sistemas de reescritura de términos (PDF) (Reporte técnico). IRIA. pag. 8. 283 . Consultado el 16 de junio de 2013 .
19. Bernhard Gramlich (junio de 1993). "Relación con la terminación más interna, débil, uniforme y modular de los sistemas de reescritura de términos". En Voronkov, Andrei (ed.). Proc. Congreso Internacional sobre Programación Lógica y Razonamiento Automatizado (LPAR) . LNAI. vol. 624. Saltador. págs. 285–296. Archivado desde el original el 4 de marzo de 2016 . Consultado el 19 de junio de 2014 .Aquí: Ejemplo 3.3
20. Yoshihito Toyama (1987). «Contraejemplos de Rescisión por Suma Directa de Sistemas de Reescritura de Término» (PDF) . inf. Proceso. Lett . 25 (3): 141-143. doi :10.1016/0020-0190(87)90122-0. hdl : 2433/99946 . Archivado (PDF) desde el original el 13 de noviembre de 2019 . Consultado el 13 de noviembre de 2019 .
21. N. Dershowitz (1985). "Terminación" (PDF) . En Jean-Pierre Jouannaud (ed.). Proc. RTA . LNCS. vol. 220. Saltador. págs. 180-224. Archivado (PDF) desde el original el 12 de noviembre de 2013 . Consultado el 16 de junio de 2013 .; aquí: p.210
22. Wolfram, DA (1993). La teoría clausal de los tipos . Prensa de la Universidad de Cambridge. págs. 47–50. doi :10.1017/CBO9780511569906. ISBN 9780521395380. S2CID  42331173.
23. Nipkow, Tobías; Prehofer, Christian (1998). "Reescritura de orden superior y razonamiento ecuacional". En Biblia, W.; Schmitt, P. (eds.). Deducción automatizada: base para las solicitudes. Tomo I: Cimentaciones . Kluwer. págs. 399–430. Archivado desde el original el 16 de agosto de 2021 . Consultado el 16 de agosto de 2021 .