Sistema de reescritura abstracta

Sistema formal para transcribir expresiones en términos equivalentes.

En lógica matemática e informática teórica , un sistema de reescritura abstracta (también sistema de reducción (abstracto) o sistema de reescritura abstracta ; abreviado ARS ) es un formalismo que captura la noción y las propiedades por excelencia de los sistemas de reescritura . En su forma más simple, una ARS es simplemente un conjunto (de "objetos") junto con una relación binaria , tradicionalmente denotada con ; esta definición se puede refinar aún más si indexamos (etiquetamos) subconjuntos de la relación binaria. A pesar de su simplicidad, una ARS es suficiente para describir propiedades importantes de sistemas de reescritura como formas normales , terminación y diversas nociones de confluencia . ${\displaystyle \rightarrow }$

Históricamente, ha habido varias formalizaciones de la reescritura en un entorno abstracto, cada una con sus idiosincrasias. Esto se debe en parte al hecho de que algunas nociones son equivalentes, ver más abajo en este artículo. La formalización que se encuentra más comúnmente en monografías y libros de texto, y que generalmente se sigue aquí, se debe a Gérard Huet (1980). ^[1]

Definición

Un sistema de reducción abstracto ( ARS ) es la noción más general (unidimensional) sobre especificar un conjunto de objetos y reglas que se pueden aplicar para transformarlos. Más recientemente, los autores también utilizan el término sistema de reescritura abstracta . ^[2] (La preferencia por la palabra "reducción" aquí en lugar de "reescritura" constituye una desviación del uso uniforme de "reescritura" en los nombres de sistemas que son particularizaciones de ARS. Debido a que la palabra "reducción" no aparece en (En los nombres de sistemas más especializados, en textos más antiguos sistema de reducción es sinónimo de ARS.) ^[3]

Un ARS es un conjunto A , cuyos elementos generalmente se denominan objetos, junto con una relación binaria en A , tradicionalmente denotada por →, y llamada relación de reducción , relación de reescritura ^[2] o simplemente reducción . ^[3] Esta terminología (arraigada) que utiliza "reducción" es un poco engañosa, porque la relación no necesariamente reduce alguna medida de los objetos.

En algunos contextos puede resultar beneficioso distinguir entre algunos subconjuntos de reglas, es decir, algunos subconjuntos de la relación de reducción →; por ejemplo, toda la relación de reducción puede consistir en reglas de asociatividad y conmutatividad . En consecuencia, algunos autores definen la relación de reducción → como la unión indexada de algunas relaciones; por ejemplo, si , la notación utilizada es (A, → ₁ , → ₂ ). ${\displaystyle {\rightarrow _{1}\cup \rightarrow _{2}}={\rightarrow }}$

Como objeto matemático, un ARS es exactamente lo mismo que un sistema de transición de estado sin etiquetar , y si la relación se considera como una unión indexada, entonces un ARS es lo mismo que un sistema de transición de estado etiquetado donde los índices son las etiquetas. Sin embargo, el enfoque del estudio y la terminología son diferentes. En un sistema de transición de estados uno está interesado en interpretar las etiquetas como acciones, mientras que en un ARS la atención se centra en cómo los objetos pueden transformarse (reescribirse) en otros. ^[4]

Ejemplo 1

Supongamos que el conjunto de objetos es T = { a , b , c } y la relación binaria está dada por las reglas a → b , b → a , a → c y b → c . Observe que estas reglas se pueden aplicar tanto a a como a b para obtener c . Además, no se puede aplicar nada a c para transformarlo más. Esta propiedad es claramente importante.

Nociones básicas

Primero defina algunas nociones y notaciones básicas. ^[5]

• ${\displaystyle {\stackrel {+}{\rightarrow }}}$es la clausura transitiva de . ${\displaystyle \rightarrow }$
• ${\displaystyle {\stackrel {*}{\rightarrow }}}$es la clausura transitiva reflexiva de , es decir, la clausura transitiva de , donde = es la relación de identidad . De manera equivalente, es el pedido anticipado más pequeño que contiene . ${\displaystyle \rightarrow }$ ${\displaystyle (\rightarrow )\cup (=)}$ ${\displaystyle {\stackrel {*}{\rightarrow }}}$ ${\displaystyle \rightarrow }$
• De manera similar, y son cierres de la relación inversa de . ${\displaystyle {\stackrel {+}{\leftarrow }}}$ ${\displaystyle {\stackrel {*}{\leftarrow }}}$ ${\displaystyle {\leftarrow }}$ ${\displaystyle {\rightarrow }}$
• ${\displaystyle \leftrightarrow }$es el cierre simétrico de , es decir, la unión de con . ${\displaystyle \rightarrow }$ ${\displaystyle \rightarrow }$ ${\displaystyle {\leftarrow }}$
• ${\displaystyle {\stackrel {*}{\leftrightarrow }}}$es el cierre simétrico transitivo reflexivo de , es decir, el cierre transitivo de . De manera equivalente, es la relación de equivalencia más pequeña que contiene . ${\displaystyle \rightarrow }$ ${\displaystyle (\leftrightarrow )\cup (=)}$ ${\displaystyle {\stackrel {*}{\leftrightarrow }}}$ ${\displaystyle \rightarrow }$

Formas normales

Un objeto x en A se llama reducible si existe algún otro y en A y ; de lo contrario se llama irreductible o forma normal . Un objeto y se llama forma normal de x si y y son irreducibles. Si x tiene una forma normal única , generalmente se denota con . En el ejemplo 1 anterior, c es una forma normal y . Si cada objeto tiene al menos una forma normal, la ARS se llama normalización . ${\displaystyle x\rightarrow y}$ ${\displaystyle x{\stackrel {*}{\rightarrow }}y}$ ${\displaystyle x\downarrow }$ ${\displaystyle c=a\downarrow =b\downarrow }$

Unibilidad

Una noción relacionada, pero más débil que la existencia de formas normales, es la de que dos objetos son unibles : se dice que x e y son unibles si existe algún z con la propiedad de que . A partir de esta definición, es evidente que se puede definir la relación de unibilidad como donde está la composición de las relaciones . La capacidad de unión suele denotarse, de forma un tanto confusa, también con , pero en esta notación la flecha hacia abajo es una relación binaria, es decir , escribimos si xey son conectables. ${\displaystyle x{\stackrel {*}{\rightarrow }}z{\stackrel {*}{\leftarrow }}y}$ ${\displaystyle {\stackrel {*}{\rightarrow }}\circ {\stackrel {*}{\leftarrow }}}$ ${\displaystyle \circ }$ ${\displaystyle \downarrow }$ ${\displaystyle x{\mathbin {\downarrow }}y}$

La propiedad Church-Rosser y las nociones de confluencia

Se dice que una ARS posee la propiedad de Church-Rosser si y sólo si implica para todos los objetos x , y . De manera equivalente, la propiedad de Church-Rosser significa que el cierre simétrico transitivo reflexivo está contenido en la relación de unibilidad. Alonzo Church y J. Barkley Rosser demostraron en 1936 que el cálculo lambda tiene esta propiedad; ^[6] de ahí el nombre de la propiedad. ^[7] En una ARS con propiedad de Church-Rosser, el problema verbal puede reducirse a la búsqueda de un sucesor común. En un sistema Church-Rosser, un objeto tiene como máximo una forma normal; es decir, la forma normal de un objeto es única si existe, pero es posible que no exista. ${\displaystyle x{\stackrel {*}{\leftrightarrow }}y}$ ${\displaystyle x{\mathbin {\downarrow }}y}$

Varias propiedades, más simples que las de Church-Rosser, le son equivalentes. La existencia de estas propiedades equivalentes permite demostrar que un sistema es Church-Rosser con menos trabajo. Además, las nociones de confluencia pueden definirse como propiedades de un objeto particular, algo que no es posible para Church-Rosser. Se dice que un ARS es, ${\displaystyle (A,\rightarrow )}$

• confluente si y sólo si para todo w , x e y en A , implica . En términos generales, la confluencia dice que no importa cómo dos caminos divergen de un ancestro común ( w ), los caminos se unen en algún sucesor común. Esta noción puede refinarse como propiedad de un objeto particular w , y llamarse confluente al sistema si todos sus elementos son confluentes. ${\displaystyle x{\stackrel {*}{\leftarrow }}w{\stackrel {*}{\rightarrow }}y}$ ${\displaystyle x{\mathbin {\downarrow }}y}$
• semiconfluente si y sólo si para todo w , x e y en A , implica . Esto se diferencia de la confluencia por la reducción en un solo paso de w a x . ${\displaystyle x\leftarrow w{\stackrel {*}{\rightarrow }}y}$ ${\displaystyle x{\mathbin {\downarrow }}y}$
• localmente confluente si y sólo si para todo w , x , y en A , implica . Esta propiedad a veces se denomina confluencia débil . ${\displaystyle x\leftarrow w\rightarrow y}$ ${\displaystyle x{\mathbin {\downarrow }}y}$

Ejemplo de un sistema de reescritura con confluencia local que no tiene la propiedad Church-Rosser

Teorema. Para una ARS las tres condiciones siguientes son equivalentes: (i) tiene la propiedad de Church-Rosser, (ii) es confluente, (iii) es semiconfluente. ^[8]

Corolario . ^[9] En una ARS confluente si entonces ${\displaystyle x{\stackrel {*}{\leftrightarrow }}y}$

• Si tanto x como y son formas normales, entonces x = y .
• Si y es una forma normal, entonces . ${\displaystyle x{\stackrel {*}{\rightarrow }}y}$

Debido a estas equivalencias, en la literatura se encuentran bastantes variaciones en las definiciones. Por ejemplo, en Terese la propiedad de Church-Rosser y la confluencia se definen como sinónimas e idénticas a la definición de confluencia presentada aquí; Church-Rosser, tal como se define aquí, permanece sin nombre, pero se proporciona como una propiedad equivalente; esta desviación de otros textos es deliberada. ^[10] Debido al corolario anterior, se puede definir una forma normal y de x como una y irreducible con la propiedad de que . Esta definición, que se encuentra en Book y Otto, es equivalente a la común dada aquí en un sistema confluente, pero es más inclusiva en un ARS no confluente. ${\displaystyle x{\stackrel {*}{\leftrightarrow }}y}$

Por otro lado, la confluencia local no es equivalente a las otras nociones de confluencia dadas en esta sección, pero es estrictamente más débil que la confluencia. El contraejemplo típico es , que es localmente confluente pero no confluente (ver imagen). ${\displaystyle \{b\rightarrow c,c\rightarrow b,b\rightarrow a,c\rightarrow d\}}$

Terminación y convergencia

Se dice que un sistema de reescritura abstracta es terminante o noetheriano si no existe una cadena infinita . (Esto solo quiere decir que la relación de reescritura es una relación noetheriana ). En una ARS terminal, cada objeto tiene al menos una forma normal, por lo que se está normalizando. Lo contrario no es cierto. En el ejemplo 1, por ejemplo, hay una cadena de reescritura infinita, es decir , aunque el sistema se esté normalizando. Una ARS confluente y terminal se denomina canónica , ^[11] o convergente . En una ARS convergente, cada objeto tiene una forma normal única. Pero es suficiente que el sistema sea confluente y se normalice para que exista una normal única para cada elemento, como se ve en el ejemplo 1. ${\displaystyle x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots }$ ${\displaystyle a\rightarrow b\rightarrow a\rightarrow b\rightarrow \cdots }$

Teorema ( lema de Newman ): una ARS terminal es confluente si y sólo si es confluente localmente.

La prueba original de Newman de 1942 de este resultado fue bastante complicada. No fue hasta 1980 que Huet publicó una prueba mucho más simple explotando el hecho de que cuando termina podemos aplicar una inducción bien fundada . ^[12] ${\displaystyle \rightarrow }$

Ver también

• Problema planteado (matemáticas) , en particular la sección sobre sistemas de reescritura abstracta.

Notas

1. Libro y Otto 1993, pag. 9
2. Terese 2003, pag. 7
3. Libro y Otto 1993, pág. 10
4. Terese 2003, págs. 7–8
5. Baader y Nipkow 1998, págs. 8-9
6. Iglesia y Rosser 1936
7. Baader y Nipkow 1998, pág. 9
8. Baader y Nipkow 1998, pág. 11
9. Baader y Nipkow 1998, pág. 12
10. Teresa 2003, pag. 11
11. Duffy 1991, pág. 153, sección 7.2.1
12. Harrison 2009, pág. 260

Referencias

• Baader, Franz ; Nipkow, Tobías (1998). Reescritura de términos y todo eso. Prensa de la Universidad de Cambridge. ISBN 9780521779203.Un libro de texto adecuado para estudiantes universitarios.
• 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. 243–320. La preimpresión de este capítulo está disponible gratuitamente a través de los autores, pero omite las cifras. 
• Libro, Ronald V .; Otto, Friedrich (1993). "1, "Sistemas de reducción abstractos"". Sistemas de reescritura de cadenas . Springer. ISBN 0-387-97965-4.
• Marc Bézem; Jan Willem Klop ; Roel de Vrijer; Terese (2003). "1". Sistemas de reescritura de términos . Prensa de la Universidad de Cambridge. ISBN 0-521-39115-6.Esta es una monografía completa. Sin embargo, utiliza una gran cantidad de notaciones y definiciones que no se encuentran comúnmente en otros lugares. Por ejemplo, la propiedad de Church-Rosser se define como idéntica a la confluencia.
• Harrison, John (2009). "4 "Igualdad"". Manual de lógica práctica y razonamiento automatizado Cambridge University Press . ISBN 978-0-521-89957-4.Reescritura abstracta desde la perspectiva práctica de la resolución de problemas en lógica ecuacional .
• Gérard Huet , Reducciones confluentes: propiedades abstractas y aplicaciones a sistemas de reescritura de términos , Journal of the ACM ( JACM ), octubre de 1980, volumen 27, número 4, págs. El artículo de Huet estableció muchos de los conceptos, resultados y notaciones modernos.
• Sinyor, J.; "El problema 3x+1 como sistema de reescritura de cadenas", Revista Internacional de Matemáticas y Ciencias Matemáticas , Volumen 2010 (2010), ID de artículo 458563, 6 páginas.
• Duffy, David A. (1991). Principios de la demostración automatizada de teoremas . Wiley.
• Iglesia, Alonso; Rosser, JB (1936). "Algunas propiedades de la conversión". Transacciones de la Sociedad Matemática Estadounidense . 39 (3): 472–482. doi : 10.2307/1989762 . ISSN  0002-9947. JSTOR  1989762.