Vereinigung und Gaußsche Eliminierung

22

Kennt jemand Referenzen, die den Zusammenhang zwischen dem Vereinigungsalgorithmus und der Gaußschen Eliminierung genau beschreiben ? Ich interessiere mich besonders für die Beziehung zwischen dreieckigen Substitutionen und LU-Zerlegungen.

Wayne Snyder und Jean Gallier erwähnen diese Analogie in ihrem Artikel "Überarbeitete Vereinigung höherer Ordnung: Komplette Sätze von Transformationen" .

reference-request lo.logic Neel Krishnaswami
quelle
7
Als Nichtfachmann hatte ich noch nie von der Verbindung gehört. Ein Hinweis, der diese Verbindung erwähnt, wäre eine schöne Ergänzung der Frage.
Tsuyoshi Ito
1
Wie sie in der Veröffentlichung p2 darlegen, handelt es sich hauptsächlich um eine Analogie, "die im Fall höherer Ordnung zusammenbricht". Es gibt einen nachweisbaren Zusammenhang oder eine Analogie zwischen Auflösung und Gauß-Eliminierung. nahe genug?
VZN
4
Ich gehe davon aus, dass Sie das bereits wissen: Der Euklid-Algorithmus, die Gaußsche Elimination, der Buchberger-Algorithmus für Grobner-Basen und die Knuth-Bendix-Vervollständigung sollen in Bezug auf Allgemeinheit und Methode eine streng zunehmende Reihenfolge bilden. Wenn die genauen Zuordnungen zwischen diesen Methoden bekannt sind, können Sie möglicherweise die obige Verbindung ableiten?
Vijay D
@VijayD: Das wusste ich eigentlich nicht! Ich weiß, was der Buchberger-Algorithmus tut, aber ich kenne den Algorithmus selbst nicht oder überhaupt nichts über seine Beziehung zur Eliminierung durch Guassian oder zur KB-Vervollständigung.
Neel Krishnaswami

Antworten:

9

Ich halte das nicht für eine Antwort. Ich benutze das Antwortfeld, um einen Kommentar auszudrucken.

Euklids GCD-Algorithmus, Gaußsche Elimination, Buchbergers Algorithmus und Knuth-Bendix bilden eine strenge Folge von Verallgemeinerungen und sind alles Beispiele für einen sogenannten Vervollständigungsalgorithmus . Es gibt auch eine enge Beziehung zwischen diesen Algorithmen und der Auflösung in der Logik. Ich kenne keine gute Referenz dafür, aber ich habe die Tatsache gesehen, die sehr oft erwähnt wurde. Diese könnten helfen.

  1. Vorgeschichte und Grundzüge des Critical-Pair / Completion-Verfahrens , Bruno Buchberger, 1987
  2. Kanonische Reduktionssysteme in der symbolischen Mathematik , Franz Winkler. Springer Link

Lassen Sie mich wissen, wenn Sie bessere Referenzen finden.

Vijay D
quelle