Penyatuan dan Penghapusan Gaussian

22

Adakah yang tahu tentang referensi yang secara tepat menjelaskan hubungan antara algoritma unifikasi dan eliminasi Gaussian? Saya sangat tertarik pada hubungan antara substitusi segitiga dan dekomposisi LU.

Wayne Snyder dan Jean Gallier menyebutkan analogi ini dalam makalah mereka, Higher-Order Unification Revisited: Complete Sets of Transformations .

reference-request lo.logic Neel Krishnaswami
sumber
7
Sebagai seorang non-pakar, saya belum pernah mendengar tentang koneksi tersebut. Beberapa referensi yang menyebutkan hubungan ini akan menjadi tambahan yang bagus untuk pertanyaan itu.
Tsuyoshi Ito
1
seperti yang mereka nyatakan dalam makalah p2, sebagian besar analogi, "yang dalam kasus tingkat tinggi rusak". ada koneksi yang dapat dibuktikan atau analogi antara resolusi & eliminasi gaussian. cukup dekat?
vzn
4
Saya berharap Anda sudah tahu ini: Algoritma Euclid, eliminasi Gaussian, algoritma Buchberger untuk basis Grobner dan penyelesaian Knuth-Bendix seharusnya membentuk urutan peningkatan ketat dalam hal generalisasi dan metode yang mereka gunakan. Jika peta yang tepat antara metode ini diketahui, mungkin Anda bisa memperoleh koneksi di atas?
Vijay D
@ VijayD: Sebenarnya saya tidak tahu itu! Saya tahu apa yang dilakukan algoritma Buchberger, tetapi saya tidak tahu algoritma itu sendiri, atau apa pun tentang hubungannya dengan penghapusan Guassian atau penyelesaian KB.
Neel Krishnaswami

Jawaban:

9

Saya tidak menganggap ini sebagai jawaban. Saya menyalahgunakan kotak jawaban untuk mencetak komentar.

Ada perasaan yang ketat di mana algoritma GCD Euclid, eliminasi Gaussian, algoritma Buchberger dan Knuth-Bendix membentuk urutan generalisasi yang ketat dan semuanya merupakan contoh dari apa yang disebut algoritma penyelesaian . Ada juga hubungan yang erat antara algoritma dan resolusi ini dalam logika. Saya tidak tahu referensi yang bagus untuk ini tetapi saya telah melihat fakta yang sangat sering disebutkan. Ini mungkin membantu.

  1. Sejarah dan fitur dasar dari prosedur pasangan kritis / penyelesaian , Bruno Buchberger, 1987
  2. Sistem Pengurangan Canonical dalam Matematika Simbolik , Franz Winkler. Tautan Springer

Beri tahu saya jika Anda menemukan referensi yang lebih baik.

Vijay D
sumber