Unificação e Eliminação Gaussiana

22

Alguém sabe de referências que explicitam precisamente a conexão entre o algoritmo de unificação e a eliminação gaussiana? Estou particularmente interessado na relação entre substituições triangulares e decomposições de LU.

Wayne Snyder e Jean Gallier mencionam essa analogia de passagem em seu artigo, Unificação de ordem superior revisitada: conjuntos completos de transformações .

reference-request lo.logic Neel Krishnaswami
fonte
7
Como não especialista, nunca tinha ouvido falar da conexão. Alguma referência que mencione essa conexão seria uma boa adição à pergunta.
Tsuyoshi Ito
1
como afirmam no artigo p2, é principalmente uma analogia ", que no caso de ordem superior se decompõe". existe uma conexão ou analogia demonstrável entre resolução e eliminação gaussiana. perto o suficiente?
vzn
4
Espero que você já saiba disso: o algoritmo de Euclid, a eliminação gaussiana, o algoritmo de Buchberger para bases de Grobner e a conclusão de Knuth-Bendix devem formar uma sequência estritamente crescente em termos de generalidade e método que eles usam. Se os mapas precisos entre esses métodos forem conhecidos, talvez você possa derivar a conexão acima?
Vijay D
@VijayD: Na verdade, eu não sabia disso! Eu sei o que o algoritmo de Buchberger faz, mas não conheço o algoritmo em si, nem nada sobre sua relação com a eliminação da Guassiana ou a conclusão da KB.
Neel Krishnaswami

Respostas:

9

Eu não considero isso uma resposta. Estou abusando da caixa de resposta para imprimir um comentário.

Existe um sentido estrito no qual o algoritmo GCD de Euclid, a eliminação gaussiana, o algoritmo de Buchberger e Knuth-Bendix formam uma sequência estrita de generalizações e são todas instâncias do que é chamado de algoritmo de conclusão . Há também uma estreita relação entre esses algoritmos e a resolução na lógica. Não conheço uma boa referência para isso, mas vi o fato mencionado com muita frequência. Isso pode ajudar.

  1. História e características básicas do procedimento de par crítico / conclusão , Bruno Buchberger, 1987
  2. Sistemas de redução canônica em matemática simbólica , Franz Winkler. Springer Link

Deixe-me saber se você encontrar melhores referências.

Vijay D
fonte