Algoritmo de finalización de Knuth-Bendix

El algoritmo de compleción de Knuth-Bendix (llamado así por Donald Knuth y Peter Bendix ^[1] ) es un algoritmo de semidecisión ^{[2] [3]} para transformar un conjunto de ecuaciones (sobre términos ) en un sistema de reescritura de términos confluente . Cuando el algoritmo tiene éxito, resuelve efectivamente el problema verbal para el álgebra especificada .

El algoritmo de Buchberger para calcular las bases de Gröbner es un algoritmo muy similar. Aunque se desarrolló de forma independiente, también puede considerarse como la instanciación del algoritmo de Knuth-Bendix en la teoría de anillos polinómicos .

Introducción

Para un conjunto E de ecuaciones, su clausura deductiva (⁎⟷mi) es el conjunto de todas las ecuaciones que se pueden derivar aplicando ecuaciones de E en cualquier orden. Formalmente, E se considera una relación binaria , (⟶mi) es su cierre de reescritura , y (⁎⟷mi) es el cierre de equivalencia de (⟶mi). Para un conjunto R de reglas de reescritura, su cierre deductivo (⁎⟶R∘⁎⟵R) es el conjunto de todas las ecuaciones que pueden confirmarse aplicando las reglas de R de izquierda a derecha a ambos lados hasta que sean literalmente iguales. Formalmente, R se considera nuevamente como una relación binaria, (⟶R) es su cierre de reescritura, (⟵R) es su recíproco , y (⁎⟶R∘⁎⟵R) es la composición relacional de sus clausuras transitivas reflexivas (⁎⟶Ry⁎⟵R).

Por ejemplo, si E = {1⋅ x = x , x ⁻¹ ⋅ x = 1, ( x ⋅ y )⋅ z = x ⋅( y ⋅ z )} son los axiomas del grupo , la cadena de derivación

a ⁻¹ ⋅( a ⋅ b )   ⁎⟷mi   ( a ⁻ 1⋅a ) ⋅b​   ⁎⟷mi   1⋅b​   ⁎⟷mi   b

demuestra que a ⁻¹ ⋅( a ⋅ b ) ⁎⟷mi b es un miembro del cierre deductivo de E. Si R = { 1⋅ x → x , x ⁻¹ ⋅ x → 1, ( x ⋅ y )⋅ z → x ⋅( y ⋅ z ) } es una versión de "regla de reescritura" de E , las cadenas de derivación

( a ⁻ 1⋅a ) ⋅b​   ⁎⟶R   1⋅b​   ⁎⟶R   B       y       B   ⁎⟵R   b

Demuestre que ( a ⁻¹ ⋅ a )⋅ b ⁎⟶R∘⁎⟵R b es un miembro del cierre deductivo de R. Sin embargo, no hay forma de derivar a ⁻¹ ⋅( a ⋅ b )⁎⟶R∘⁎⟵R b similar a lo anterior, ya que no se permite una aplicación de derecha a izquierda de la regla ( x ⋅ y )⋅ z → x ⋅( y ⋅ z ) .

El algoritmo de Knuth-Bendix toma un conjunto E de ecuaciones entre términos y un orden de reducción (>) en el conjunto de todos los términos, e intenta construir un sistema de reescritura de términos confluente y terminal R que tenga el mismo cierre deductivo que E. Si bien demostrar consecuencias a partir de E a menudo requiere intuición humana, demostrar consecuencias a partir de R no. Para obtener más detalles, consulte Confluencia (reescritura abstracta)#Ejemplos motivadores , que brinda un ejemplo de prueba a partir de la teoría de grupos, realizada tanto con E como con R.

Normas

Dado un conjunto E de ecuaciones entre términos , se pueden usar las siguientes reglas de inferencia para transformarlo en un sistema de reescritura de términos convergente equivalente (si es posible): ^{[4] [5]} Se basan en un ordenamiento de reducción dado por el usuario (>) en el conjunto de todos los términos; se eleva a un ordenamiento bien fundado (▻) en el conjunto de reglas de reescritura definiendo ( s → t ) ▻ ( l → r ) si

• s >mi l en el ordenamiento abarcativo , o
• s y l son literalmente similares y t > r .

Ejemplo

El siguiente ejemplo de ejecución, obtenido del demostrador de teoremas E , calcula una completitud de los axiomas de grupo (aditivos) como en Knuth, Bendix (1970). Comienza con las tres ecuaciones iniciales para el grupo (elemento neutro 0, elementos inversos, asociatividad), utilizando f(X,Y)para X + Y y i(X)para − X. Las 10 ecuaciones marcadas con asterisco resultan constituir el sistema de reescritura convergente resultante. "pm" es la abreviatura de " paramodulación ", que implementa deduce . El cálculo de pares críticos es una instancia de paramodulación para cláusulas unitarias ecuacionales. "rw" es reescritura, que implementa compose , collapse y simplify . La orientación de las ecuaciones se realiza de forma implícita y no se registra.

Véase también Problema de palabras (matemáticas) para otra presentación de este ejemplo.

Sistemas de reescritura de cuerdas en la teoría de grupos

Un caso importante en la teoría de grupos computacionales son los sistemas de reescritura de cadenas que se pueden utilizar para dar etiquetas canónicas a elementos o clases laterales de un grupo finitamente presentado como productos de los generadores . Este caso especial es el foco de esta sección.

La motivación en la teoría de grupos

El lema del par crítico establece que un sistema de reescritura de términos es localmente confluente (o débilmente confluente) si y solo si todos sus pares críticos son convergentes. Además, tenemos el lema de Newman que establece que si un sistema de reescritura (abstracto) es fuertemente normalizante y débilmente confluente, entonces el sistema de reescritura es confluente. Por lo tanto, si podemos agregar reglas al sistema de reescritura de términos para forzar que todos los pares críticos sean convergentes mientras se mantiene la propiedad de fuerte normalización, entonces esto forzará al sistema de reescritura resultante a ser confluente.

Consideremos un monoide finitamente presentado donde X es un conjunto finito de generadores y R es un conjunto de relaciones definitorias en X. Sea X ^* el conjunto de todas las palabras en X (es decir, el monoide libre generado por X). Puesto que las relaciones R generan una relación de equivalencia en X*, se pueden considerar los elementos de M como las clases de equivalencia de X ^* bajo R. Para cada clase {w ₁ , w ₂ , ... } es deseable elegir un representante estándar w _k . Este representante se llama forma canónica o normal para cada palabra w _k en la clase. Si hay un método computable para determinar para cada w _k su forma normal w _i entonces el problema de palabras se resuelve fácilmente. Un sistema de reescritura confluente permite hacer precisamente esto. ${\displaystyle M=\langle X\mid R\rangle }$

Aunque la elección de una forma canónica puede hacerse teóricamente de manera arbitraria, este enfoque generalmente no es computable. (Considere que una relación de equivalencia en un lenguaje puede producir un número infinito de clases infinitas). Si el lenguaje está bien ordenado , entonces el orden < proporciona un método consistente para definir representantes mínimos, sin embargo, el cálculo de estos representantes puede no ser posible. En particular, si se utiliza un sistema de reescritura para calcular representantes mínimos, entonces el orden < también debería tener la propiedad:

A < B → XAY < XBY para todas las palabras A,B,X,Y

Esta propiedad se denomina invariancia de la traducción . Un orden que es invariante en la traducción y al mismo tiempo un buen orden se denomina orden de reducción .

A partir de la presentación del monoide es posible definir un sistema de reescritura dado por las relaciones R. Si A x B está en R entonces A < B en cuyo caso B → A es una regla en el sistema de reescritura, de lo contrario A > B y A → B. Como < es un orden de reducción, una palabra dada W puede reducirse W > W_1 > ... > W_n donde W_n es irreducible bajo el sistema de reescritura. Sin embargo, dependiendo de las reglas que se apliquen en cada W _i  → W _i+1 es posible terminar con dos reducciones irreducibles diferentes W _n  ≠ W' _m de W. Sin embargo, si el sistema de reescritura dado por las relaciones se convierte a un sistema de reescritura confluente mediante el algoritmo de Knuth-Bendix, entonces se garantiza que todas las reducciones producirán la misma palabra irreducible, es decir, la forma normal para esa palabra.

Descripción del algoritmo para monoides presentados finitamente

Supongamos que se nos da una presentación , donde es un conjunto de generadores y es un conjunto de relaciones que dan el sistema de reescritura. Supongamos además que tenemos un orden de reducción entre las palabras generadas por (por ejemplo, orden shortlex ). Para cada relación en , supongamos . Por lo tanto, comenzamos con el conjunto de reducciones . ${\displaystyle \langle X\mid R\rangle }$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle <}$ ${\displaystyle X}$ ${\displaystyle P_{i}=Q_{i}}$ ${\displaystyle R}$ ${\displaystyle Q_{i}<P_{i}}$ ${\displaystyle P_{i}\rightarrow Q_{i}}$

Primero, si alguna relación se puede reducir, reemplace y con las reducciones. ${\displaystyle P_{i}=Q_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle Q_{i}}$

A continuación, añadimos más reducciones (es decir, reescribimos las reglas) para eliminar posibles excepciones de confluencia. Supongamos que y se superponen. ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$

1. Caso 1: o bien el prefijo de es igual al sufijo de , o viceversa. En el primer caso, podemos escribir y ; en el segundo caso, y . ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{i}=BC}$ ${\displaystyle P_{j}=AB}$ ${\displaystyle P_{i}=AB}$ ${\displaystyle P_{j}=BC}$
2. Caso 2: o bien está completamente contenido en (rodeado por) , o viceversa. En el primer caso, podemos escribir y ; en el segundo caso, y . ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{i}=B}$ ${\displaystyle P_{j}=ABC}$ ${\displaystyle P_{i}=ABC}$ ${\displaystyle P_{j}=B}$

Reducir la palabra usando primero, luego usando primero. Llamar a los resultados , respectivamente. Si , entonces tenemos una instancia en la que la confluencia podría fallar. Por lo tanto, agregar la reducción a . ${\displaystyle ABC}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$ ${\displaystyle r_{1},r_{2}}$ ${\displaystyle r_{1}\neq r_{2}}$ ${\displaystyle \max r_{1},r_{2}\rightarrow \min r_{1},r_{2}}$ ${\displaystyle R}$

Después de agregar una regla a , elimine cualquier regla que pueda tener lados izquierdos reducibles (después de verificar si dichas reglas tienen pares críticos con otras reglas). ${\displaystyle R}$ ${\displaystyle R}$

Repita el procedimiento hasta que se hayan comprobado todos los lados izquierdos superpuestos.

Ejemplos

Un ejemplo final

Consideremos el monoide:

${\displaystyle \langle x,y\mid x^{3}=y^{3}=(xy)^{3}=1\rangle }$.

Usamos el orden shortlex . Este es un monoide infinito, pero, sin embargo, el algoritmo de Knuth-Bendix es capaz de resolver el problema verbal.

Nuestras tres reducciones iniciales son por lo tanto

Un sufijo de (a saber , ) es un prefijo de , por lo que considera la palabra . Reduciendo usando ( 1 ), obtenemos . Reduciendo usando ( 3 ), obtenemos . Por lo tanto, obtenemos , dando la regla de reducción ${\displaystyle x^{3}}$ ${\displaystyle x}$ ${\displaystyle (xy)^{3}=xyxyxy}$ ${\displaystyle x^{3}yxyxy}$ ${\displaystyle yxyxy}$ ${\displaystyle x^{2}}$ ${\displaystyle yxyxy=x^{2}}$

De manera similar, usando y reduciendo usando ( 2 ) y ( 3 ), obtenemos . Por lo tanto, la reducción ${\displaystyle xyxyxy^{3}}$ ${\displaystyle xyxyx=y^{2}}$

Ambas reglas están obsoletas ( 3 ), por eso las eliminamos.

A continuación, considere superponiendo ( 1 ) y ( 5 ). Reduciendo obtenemos , por lo que agregamos la regla ${\displaystyle x^{3}yxyx}$ ${\displaystyle yxyx=x^{2}y^{2}}$

Considerando superponiendo ( 1 ) y ( 5 ), obtenemos , por lo que agregamos la regla ${\displaystyle xyxyx^{3}}$ ${\displaystyle xyxy=y^{2}x^{2}}$

Estas reglas están obsoletas ( 4 ) y ( 5 ), por lo que las eliminamos.

Ahora, nos queda el sistema de reescritura.

Al comprobar las superposiciones de estas reglas, no encontramos posibles fallos de confluencia. Por lo tanto, tenemos un sistema de reescritura confluente y el algoritmo finaliza con éxito.

Un ejemplo que no termina

El orden de los generadores puede afectar de manera crucial si la compleción de Knuth-Bendix termina o no. Como ejemplo, considere el grupo abeliano libre por la presentación monoide:

${\displaystyle \langle x,y,x^{-1},y^{-1}\,|\,xy=yx,xx^{-1}=x^{-1}x=yy^{-1}=y^{-1}y=1\rangle .}$

La completitud de Knuth-Bendix con respecto al orden lexicográfico finaliza con un sistema convergente, sin embargo, considerando el orden lexicográfico de longitud, no finaliza porque no hay sistemas convergentes finitos compatibles con este último orden. ^[6] ${\displaystyle x<x^{-1}<y<y^{-1}}$ ${\displaystyle x<y<x^{-1}<y^{-1}}$

Generalizaciones

Si Knuth–Bendix no tiene éxito, o bien se ejecutará eternamente y producirá aproximaciones sucesivas a un sistema completo infinito, o bien fallará cuando encuentre una ecuación no orientable (es decir, una ecuación que no pueda convertir en una regla de reescritura). Una versión mejorada no fallará en ecuaciones no orientables y producirá un sistema confluente básico , lo que proporciona un semialgoritmo para el problema verbal. ^[7]

La noción de reescritura registrada que se analiza en el artículo de Heyworth y Wensley que se incluye a continuación permite registrar o registrar el proceso de reescritura a medida que avanza. Esto resulta útil para calcular identidades entre relaciones para presentaciones de grupos.

Referencias

1. D. Knuth, "La génesis de las gramáticas de atributos"
2. Jacob T. Schwartz; Domenico Cantone; Eugenio G. Omodeo; Martin Davis (2011). Lógica computacional y teoría de conjuntos: aplicación de la lógica formalizada al análisis . Springer Science & Business Media. pág. 200. ISBN 978-0-85729-808-9.
3. Hsiang, J.; Rusinowitch, M. (1987). "Sobre problemas verbales en teorías ecuacionales" (PDF) . Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 267. pág. 54. doi :10.1007/3-540-18088-5_6. ISBN. 978-3-540-18088-3., pág. 55
4. Bachmair, L.; Dershowitz, N.; Hsiang, J. (junio de 1986). "Ordenamientos para pruebas ecuacionales". Proc. Simposio IEEE sobre lógica en informática . págs. 346–357.
5. N. Dershowitz; J.-P. Jouannaud (1990). Jan van Leeuwen (ed.). Rewrite Systems . Manual de informática teórica. Vol. B. Elsevier. págs. 243–320.Aquí: secc.8.1, p.293
6. V. Diekert; AJ Duncan; AG Myasnikov (2011). "Sistemas de reescritura geodésica y pregrupos". En Oleg Bogopolski; Inna Bumagin; Olga Kharlampovich; Enric Ventura (eds.). Teoría combinatoria y de grupos geométricos: conferencias de Dortmund y Ottawa-Montreal . Springer Science & Business Media. pág. 62. ISBN 978-3-7643-9911-5.
7. Bachmair, Leo; Dershowitz, Nachum; Plaisted, David A. (1989). "Completion Without Failure" (PDF) . Técnicas de reescritura : 1–30. doi :10.1016/B978-0-12-046371-8.50007-9 . Consultado el 24 de diciembre de 2021 .

• D. Knuth; P. Bendix (1970). J. Leech (ed.). Problemas verbales sencillos en álgebras universales (PDF) . Pergamon Press. págs. 263–297.
• Gérard Huet (1981). "Una prueba completa de la corrección del algoritmo de compleción de Knuth-Bendix" (PDF) . J. Comput. Syst. Sci . 23 (1): 11–21. doi :10.1016/0022-0000(81)90002-7.
• C. Sims. 'Cálculos con grupos finitamente presentados'. Cambridge, 1994.
• Anne Heyworth y CD Wensley. "Reescritura registrada e identidades entre relatores". Grupos St. Andrews 2001 en Oxford. Vol. I, 256–276, London Math. Soc. Lecture Note Ser., 304, Cambridge Univ. Press, Cambridge, 2003.

Enlaces externos

• Weisstein, Eric W. "Algoritmo de finalización de Knuth-Bendix". MundoMatemático .
• Visualizador de finalización de Knuth-Bendix