Unificación y eliminación gaussiana

22

¿Alguien sabe de referencias que explican con precisión la conexión entre el algoritmo de unificación y la eliminación gaussiana? Estoy particularmente interesado en la relación entre las sustituciones triangulares y las descomposiciones LU.

Wayne Snyder y Jean Gallier mencionan esta analogía de pasada en su artículo, Unificación de orden superior revisada: conjuntos completos de transformaciones .

reference-request lo.logic Neel Krishnaswami
fuente
77
Como no experto, nunca había oído hablar de la conexión. Alguna referencia que mencione esta conexión sería una buena adición a la pregunta.
Tsuyoshi Ito
1
Como dicen en el documento p2, es principalmente una analogía, "que en el caso de orden superior se descompone". Existe una conexión o analogía demostrable entre la resolución y la eliminación gaussiana. ¿suficientemente cerca?
vzn
44
Espero que ya lo sepas: el algoritmo de Euclides, la eliminación gaussiana, el algoritmo de Buchberger para las bases de Grobner y la finalización de Knuth-Bendix se supone que forman una secuencia estrictamente creciente en términos de generalidad y método que utilizan. Si se conocen los mapas precisos entre estos métodos, ¿tal vez podría derivar la conexión anterior?
Vijay D
@VijayD: ¡No sabía eso, en realidad! Sé lo que hace el algoritmo de Buchberger, pero no sé el algoritmo en sí mismo, ni nada en absoluto sobre su relación con la eliminación de Guassian o la finalización de KB.
Neel Krishnaswami

Respuestas:

9

No considero esto una respuesta. Estoy abusando del cuadro de respuesta para imprimir un comentario bonito.

Hay un sentido estricto en el que el algoritmo GCD de Euclides, la eliminación gaussiana, el algoritmo de Buchberger y Knuth-Bendix forman una secuencia estricta de generalizaciones y son todas instancias de lo que se llama un algoritmo de finalización . También existe una estrecha relación entre estos algoritmos y la resolución en la lógica. No conozco una buena referencia para esto, pero he visto el hecho mencionado muy a menudo. Estos pueden ayudar.

  1. Historia y características básicas del procedimiento de par crítico / finalización , Bruno Buchberger, 1987
  2. Sistemas de reducción canónica en matemática simbólica , Franz Winkler. Enlace Springer

Avísame si encuentras mejores referencias.

Vijay D
fuente