Wofür werden Gitter verwendet?

Question

Wikipedia sagt:

Komplette Gitter erscheinen in vielen Anwendungen in Mathematik und Informatik

Bezieht es sich nur auf die Tatsache, dass die in der Berechnung verwendete Standard -Boolesche Algebra ein komplettes Gitter ist? Gibt es irgendetwas, das wir gewinnen, indem wir auf der stellvertretenden Ebene der Gitter und nicht in der Booleschen Logik arbeiten?

Eine Google -Suche findet nicht viel zu diesem Thema, aber ich verwende wahrscheinlich die falschen Schlüsselwörter.

Answer 1

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

Teilweise Ordnung und Gittertheorie spielen jetzt eine wichtige Rolle in vielen Disziplinen von Informatik und Ingenieurwesen. Beispielsweise haben sie Anwendungen im verteilten Computing (Vektoruhren, globaler Prädikaterkennung), die Genauigkeitstheorie (Pomsets, Vorkommensnetze), die Semantik der Programmiersprache (Festpunktsemantik) und Data Mining (Konzeptanalyse). Sie sind auch in anderen Disziplinen von Mathematik wie Kombinatorik, Zahlentheorie und Gruppentheorie nützlich. In diesem Buch stelle ich wichtige Ergebnisse in der teilweisen Ordnungstheorie zusammen mit ihren Anwendungen in der Informatik ein. Die Verzerrung des Buches befasst sich mit rechnerischen Aspekten der Gittertheorie (Algorithmen) und auf Anwendungen (insbesondere verteilte Systeme).

Das Buch scheint die Rekursionstheorie (Theorie der berechnbaren Mengen) nicht zu erwähnen, sondern aus Wikipedias Artikel über Computerbarkeitstheorie, wir sehen:

Als Post den Begriff eines einfachen Satzes als RE -Set mit einem unendlichen Komplement definierte, das keine unendliche R -Set enthält, begann er, die Struktur der rekursiv aufzählbaren Sätze unter Einschluss zu untersuchen. Dieses Gitter wurde zu einer gut untersuchten Struktur. Rekursive Sets können in dieser Struktur durch das Grundergebnis definiert werden, dass ein Satz nur dann rekursiv ist, wenn der Satz und seine Komplement rekursiv aufgezählt werden. Unendliche RE -Sets haben immer unendliche rekursive Untergruppen; Andererseits existieren jedoch einfache Sets, haben aber keine musklearische rekursive Superset. Post (1944) führte bereits hypersimple und hyperhypersimple -Sets ein; Spätere maximale Sets wurden konstruiert, die RE-Sätze sind, so dass jeder RE-Superset entweder eine endliche Variante des gegebenen maximalen Satzes oder Co-Finite ist. Die ursprüngliche Motivation von Post bei der Untersuchung dieses Gitters bestand darin, einen strukturellen Begriff zu finden, so dass jedes Satz, der diese Eigenschaft erfüllt, weder im Turing -Grad der rekursiven Sätze noch im turenden Grad des Störproblems liegt. Post fand keine solche Eigenschaft und die Lösung für seine problematischen Prioritätsmethoden statt. Harrington und Soare (1991) fanden schließlich ein solches Eigentum.

Weitere Lektüren finden Sie im Blog -Beitrag Gittertheorie für Programmierer und Nicht -Informatiker.

Answer 2

Die von Pål GD angegebenen Referenzen sind in der Tat sehr geeignet. Konzentrieren wir uns also stattdessen auf eine kleine Seite in dieser Antwort. Ich habe vor einiger Zeit einige Laut in Gitter gelesen und mich gefragt, ob der Begriff des Semilattice nicht für Bewerbungen geeigneter gewesen wäre. Sie mögen Einwände erheben, dass ein komplettes Halbgitter automatisch auch ein Gitter ist, aber die Homomorphismen und Unterstrukturen (dh Sublattices und Subsemilattices) sind unterschiedlich.

Ich habe zuerst (Semi-) Gitter bei der Studie von Semigroups als kommutative idempotente Semigroups begegnet. Dann dachte ich über die Beziehung zwischen hierarchischen Strukturen und Gitter nach und bemerkte, dass ein Baum von Natur aus auch ein Semilattice ist. Dann fand ich Gitter in Sicherheitskontexten und in der Programmanalyse, und es schien mir immer so, als wäre die Semilattice -Struktur der wirklich wichtige Teil, und das Gitter wurde nur genommen, weil es "kostenlos" erhalten werden konnte. Selbst für eine Heyting -Algebra gibt es eine Asymmetrie zwischen Konjunktion und Disjunktion, die mir darauf hindeutet, dass das asymmetrische Semilattice -Modell hier möglicherweise mehr Einblicke liefern als das symmetrische Gittermodell.

Answer 3

Ein sehr wichtiger, aber nicht so berühmter Fall-er ist unter den Theoretikern bekannt, aber nicht so bekannt im Sinne des Lehren der Studenten-, ist die Verwendung eines Gitters zu beweisen Superpolynom untere Grenzen auf der Größe der Monotonschaltkreise Computing Clique für welche Razborov gewann das NevanLinna -Preis. Die ursprüngliche Konstruktion ist jedoch sehr technisch und später Konstruktionen z. Berg/Ulfberg Vereinfachen Sie den Framework ohne Verweis auf Gitter.

In diesem Fall wurde die Gittertheorie als Rahmen verwendet, um den ursprünglichen Beweis zu entdecken, aber spätere Formulierungen neigten dazu, sie nicht direkt als konzeptionelle Vereinfachung zu bezeichnen.

Ja, JA -Gitter können also als exotischeres mathematischeres Objekt angesehen werden [Razborov hat an anderer Stelle über seinen Stil gesprochen, fortgeschrittene Mathematik auf CS anzuwenden, die einem anderen "konkreten" Objekt in CS entsprechen könnten, in diesem Fall "Approximation Gates" sind IE boolean Gates in Schaltungen, die "ungefähr korrekte" Antworten geben und welche Gitter eine Art "Induktionsstruktur" für die Umwandlung zwischen einer genauen Schaltung in einen approximierten Schaltkreis sind.

Answer 4

Ich habe seitdem das kostenlose Papier gefunden Bestellte Sets und vollständige Gitter: Ein Primer für Informatik, für andere interessierte Leser.

Answer 5

Reguläre Kantenbezeichnungen und verwandte Strukturen bilden ein verteilendes Gitter (siehe zum Beispiel hier). Dies kann genutzt werden, um effizient im Raum aller regulären Kantenbezeichnungen nach einem bestimmten Diagramm zu suchen (siehe hier). Als Anwendung können Sie feststellen, ob eine Karte als gezeichnet werden kann Kartogramm mit einer bestimmten Flächenaufgabe für die Gesichter.

Answer 6

Auch überraschenderweise (zumindest für mich) Kryptographie. Probieren Sie es aus, es ermöglicht neue Angriffe bekannter Kryptosysteme und gibt Hoffnungen auf die Kryptographie nach der Quantum.