Wofür werden Gitter verwendet?

15

Wikipedia sagt :

Komplette Gitter erscheinen in vielen Anwendungen in Mathematik und Informatik

Bezieht es sich nur auf die Tatsache, dass die zur Berechnung verwendete Standard-Boolesche Algebra ein vollständiges Gitter ist? Gibt es irgendetwas, das wir gewinnen, wenn wir auf der abstrakten Ebene von Gittern anstatt speziell mit Boolescher Logik arbeiten?

Eine Google-Suche findet nicht viel zu diesem Thema, aber ich verwende wahrscheinlich die falschen Keywords.

Xodarap
quelle
en.wikipedia.org/wiki/Intuitionistic_logic und andere nicht-klassische Logiken verwenden verschiedene Arten von vollständigen Gittern für ihre Semantik.
András Salamon

Antworten:

11

Siehe zum Beispiel dieses Buch: Gittertheorie mit Anwendungen, Vijay K. Garg , das wie folgt beginnt:

Partielle Ordnungs- und Gittertheorie spielen heute in vielen Disziplinen der Informatik und Ingenieurwissenschaften eine wichtige Rolle. Beispielsweise finden sie Anwendungen im verteilten Rechnen (Vektoruhren, Erkennung globaler Prädikate), in der Theorie der Parallelität (Pomsets, Vorkommensnetze), in der Semantik von Programmiersprachen (Festkommasemantik) und im Data Mining (Konzeptanalyse). Sie sind auch in anderen mathematischen Disziplinen wie der Kombinatorik, der Zahlentheorie und der Gruppentheorie nützlich. In diesem Buch stelle ich wichtige Ergebnisse der Teilordnungstheorie sowie deren Anwendungen in der Informatik vor. Der Schwerpunkt des Buches liegt auf rechnerischen Aspekten der Gittertheorie (Algorithmen) und auf Anwendungen (va verteilte Systeme).

Das Buch scheint die Rekursionstheorie (Theorie der berechenbaren Mengen) nicht zu erwähnen, aber aus dem Wikipedia-Artikel zur Berechenbarkeitstheorie sehen wir:

Als Post den Begriff einer einfachen Menge als eine Neueinstellung mit einem unendlichen Komplement definierte, das keine unendliche Neueinstellung enthielt, begann er, die Struktur der rekursiv aufzählbaren Mengen unter Einschluss zu untersuchen. Dieses Gitter wurde zu einer gut untersuchten Struktur. Rekursive Mengen können in dieser Struktur durch das grundlegende Ergebnis definiert werden, dass eine Menge nur dann rekursiv ist, wenn sowohl die Menge als auch ihr Komplement rekursiv aufzählbar sind. Unendliche Resets haben immer unendliche rekursive Subsets; Andererseits existieren einfache Mengen, die jedoch keine koinfinite rekursive Obermenge haben. Post (1944) führte bereits hypersimple und hyperhypersimple Mengen ein; Später wurden Maximalsätze konstruiert, die Resätze sind, so dass jeder Resatz entweder eine endliche Variante des gegebenen Maximalsatzes ist oder co-endlich ist. Post' Die ursprüngliche Motivation bei der Untersuchung dieses Gitters bestand darin, einen Strukturbegriff zu finden, der besagt, dass jede Menge, die diese Eigenschaft erfüllt, weder im Turing-Grad der rekursiven Mengen noch im Turing-Grad des Halteproblems liegt. Post fand keine solche Eigenschaft und die Lösung seines Problems verwendete stattdessen Prioritätsmethoden. Harrington und Soare (1991) fanden schließlich eine solche Eigenschaft.

Weitere Informationen finden Sie im Blog-Beitrag Lattice Theory for Programmers and Non Computer Scientists .

Pål GD
quelle
2
Lassen Sie mich noch hinzufügen, dass Gitter und der damit verbundene Domänenbegriff in der Semantik von Programmiersprachen häufig verwendet werden.
Andrej Bauer
@AndrejBauer könntest du ein paar Hinweise auf Beispiele geben? Vielen Dank.
Uhr
3

Die Referenzen von Pål GD sind in der Tat sehr zutreffend. Konzentrieren wir uns in dieser Antwort stattdessen auf ein Nebenproblem. Ich habe vor einiger Zeit einige Lektionen über Gitter durchgeführt und mich gefragt, ob der Begriff Semilattice für Anwendungen nicht geeigneter gewesen wäre. Sie könnten einwenden, dass ein vollständiges Halbgitter automatisch auch ein Gitter ist, aber die Homomorphismen und Unterstrukturen (dh Untergitter und Untergitter) sind unterschiedlich.

Beim Studium von Halbgruppen bin ich zum ersten Mal auf (Halb-) Gitter gestoßen, als kommutative idempotente Halbgruppen. Dann habe ich über die Beziehung zwischen hierarchischen Strukturen und Gittern nachgedacht und festgestellt, dass ein Baum natürlich auch ein Halbgitter ist. Dann fand ich Gitter in Sicherheitskontexten und in der Programmanalyse, und es schien mir immer, als sei die Semilattice-Struktur der wirklich wichtige Teil, und das Gitter wurde einfach genommen, weil es "kostenlos" erhalten werden konnte. Sogar für eine Heyting-Algebra gibt es eine Asymmetrie zwischen Konjunktion und Disjunktion, die mir nahelegt, dass das asymmetrische Halbgittermodell hier mehr Einsicht bieten könnte als das symmetrische Gittermodell.

Thomas Klimpel
quelle
1
Können Sie erläutern, wie Bäume Halbgitter sind? Und vor allem, wenn es interessante Theoreme gibt, die wir mit (Halb-) Gittern über Datenstrukturen beweisen können?
Xodarap
@Xodarap Wenn wir einen Baum als eine teilweise geordnete Menge betrachten, wird die Verknüpfung zweier Knoten durch ihren niedrigsten gemeinsamen Vorfahren angegeben. In Bezug auf Ihre Anfrage zu Datenstrukturen hängt dies vermutlich mit meiner früheren Frage zur Datenstruktur für Halbgitter zusammen . Mein Fazit war damals, dass es sich um ein überraschend nicht triviales Problem handelt. Außerdem hatte ich nicht die Absicht, mich zu weit vom Mainstream zu entfernen, und war daher sehr froh, diesen Blogpost mit dem tollen Referenzteil zu finden.
Thomas Klimpel
3

Ein sehr wichtiger, aber nicht so berühmter Fall - bekannt unter Theoretikern, aber nicht so bekannt im Sinne einer Lehre für Studenten - der Einsatz eines Gitters ist der Nachweis von superpolynomialen Untergrenzen für die Größe monotoner Schaltkreise Computing-Clique, für die Rasborow den Nevanlinna-Preis gewann . Die ursprüngliche Konstruktion ist jedoch sehr technisch und spätere Konstruktionen, z. B. Berg / Ulfberg, vereinfachen den Rahmen ohne den Hinweis auf Gitter.

In diesem Fall wurde die Gittertheorie als Rahmen verwendet, um den ursprünglichen Beweis zu finden. Spätere Formulierungen tendierten jedoch dazu, ihn nicht direkt als konzeptionelle Vereinfachung zu bezeichnen.

ja, Gitter können als exotischeres mathematisches Objekt angesehen werden [Razborov hat an anderer Stelle von seinem Stil gesprochen, fortgeschrittene Mathematik auf CS anzuwenden], das einem anderen "konkreteren" Objekt in CS entsprechen könnte, in diesem Fall handelt es sich um "Approximationsgatter". dh boolesche Gatter in Schaltkreisen, die "annähernd korrekte" Antworten geben und deren Gitter eine Art "Induktionsstruktur" ist, um zwischen einem genauen Schaltkreis in einen ungenauen, annähernden Schaltkreis umzuwandeln.

vzn
quelle
2

Regelmäßige Kantenbeschriftungen und verwandte Strukturen bilden ein Verteilungsgitter (siehe hier ). Dies kann ausgenutzt werden, um den Raum aller regulären Kantenbeschriftungen für ein bestimmtes Diagramm effizient zu durchsuchen (siehe hier ). Als Anwendung können Sie festlegen, ob eine Karte als Kartogramm mit einer bestimmten Bereichszuordnung für die Gesichter gezeichnet werden kann .

A.Schulz
quelle
2

Überraschenderweise (zumindest für mich) auch Kryptografie . Probieren Sie es aus, es ermöglicht neue Angriffe auf bekannte Kryptosysteme und gibt Hoffnung auf Kryptographie nach dem Quanten-Computing.

Helios
quelle
2
Diese Art von "periodischem" Gitter ist nicht dasselbe, nach dem das OP fragt. Die Frage ist, ob Strukturen mit binären Operationen sich treffen und verbinden.
András Salamon
Hoppla. Dann habe ich überhaupt nicht verstanden, worum es beim OP ging.
Helios
Aber die Gitter, von denen Helios spricht, sind tatsächlich Verteilungsgitter in der üblichen Dominanzreihenfolge. Auch und ich kann mich irren, aber ich denke, dass jedes Verteilungsgitter als Teilmenge eines periodischen Gitters in den Raum eingebettet werden kann. Und sie sind derzeit wohl die aufregendste Sache in der Kryptographie.
Sasho Nikolov