Verwendung algebraischer Strukturen in der theoretischen Informatik

67

Ich bin ein Software-Praktiker und schreibe eine Umfrage zu algebraischen Strukturen für die persönliche Forschung. Ich versuche Beispiele zu liefern, wie diese Strukturen in der theoretischen Informatik (und in geringerem Maße in anderen Teilbereichen der Informatik) verwendet werden. .

In der Gruppentheorie bin ich auf syntaktische Monoide für formale Sprachen und Trace- und History-Monoide für paralleles / gleichzeitiges Rechnen gestoßen.

Vom Standpunkt der Ringtheorie aus bin ich auf semiringbasierte Frameworks für die Graphverarbeitung und semiringbasiertes Parsen gestoßen.

Ich habe noch keine Verwendung für algebraische Strukturen aus der Modultheorie in meiner Forschung gefunden (und möchte dies auch tun).

Ich gehe davon aus, dass es weitere Beispiele gibt und dass ich einfach nicht an der richtigen Stelle suche, um sie zu finden.

Was sind einige andere Beispiele für algebraische Strukturen aus den oben aufgeführten Bereichen, die in der theoretischen Informatik (und anderen Teilgebieten der Informatik) häufig anzutreffen sind? Welche Zeitschriften oder anderen Ressourcen können Sie alternativ empfehlen, um diese Themen abzudecken?

GEL
quelle
12
Das scheint ziemlich groß zu sein. Alle Arten von algebraischen Strukturen (Gruppen, Ringe, Semiringe, Halbgruppen, Felder) tauchen in der theoretischen Informatik auf, und es ist allgegenwärtig genug, dass es Ihnen schwer fällt, eine bestimmte Unterkomponente zu finden. Vergessen Sie auch nicht, endliche Felder für das Hashing und viele andere zufällige Fingerabdruckmethoden zu verwenden.
Suresh Venkat
3
Möglicherweise hat alles, was darstellbar sein kann, eine Verwendung in der Informatik!
vs

Antworten:

46

Mein Eindruck ist, dass die traditionelle Algebra im Großen und Ganzen zu spezifisch für den Einsatz in der Informatik ist. Daher verwenden Informatiker entweder schwächere (und daher allgemeinere) Strukturen oder verallgemeinern die traditionellen Strukturen, damit sie sie an ihre Bedürfnisse anpassen können. Wir verwenden auch viel Kategorietheorie, die Mathematiker nicht als Teil der Algebra betrachten, aber wir sehen nicht, warum nicht. Wir finden die Reglementierung der traditionellen Mathematik in "Algebra" und "Topologie" als getrennte Zweige unpraktisch, sogar sinnlos, weil Algebra im Allgemeinen erster Ordnung ist, während Topologie die Möglichkeit hat, mit Aspekten höherer Ordnung umzugehen. Die in der Informatik verwendeten Strukturen weisen also eine Vermischung von Algebra und Topologie auf. Tatsächlich tendieren sie eher zur Topologie als zur Algebra. Die Reglementierung des Denkens in "Algebra" und "Logik" ist aus unserer Sicht eine weitere sinnlose Unterteilung, da sich die Algebra auch mit Gleichungseigenschaften befasst, wohingegen sich die Logik auch mit allen anderen Arten von Eigenschaften befasst.

Um auf Ihre Frage zurückzukommen: Halbgruppen und Monoide werden in der Automatentheorie sehr intensiv verwendet. Eilenberg hat eine 2-bändige Sammlung verfasst , von der die zweite fast ausschließlich Algebra ist. Mir wurde gesagt, dass er vier Bände plante, aber sein Alter erlaubte nicht, dass das Projekt abgeschlossen wurde. Jean-Eric Pin hat eine modernisierte Version vieler dieser Inhalte in einem Online-Buch . Automaten sind "monoide Module" (auch "Monoid Actions" oder "Acts" genannt), die für die Informatik die richtige Allgemeingültigkeit besitzen. Herkömmliche Ringmodule sind wahrscheinlich zu spezifisch.

Die Gittertheorie war eine wichtige Kraft bei der Entwicklung der Denotationssemantik. Die Topologie wurde in die Gittertheorie eingemischt, als Informatiker gemeinsam mit Mathematikern kontinuierliche Gitter entwickelten und diese dann auf Domänen verallgemeinerten . Ich würde sagen, dass die Domänentheorie die Mathematik von Informatikern ist, über die die traditionelle Mathematik keine Kenntnisse hat.

Universalalgebra wird zum Definieren algebraischer Spezifikationen von Datentypen verwendet . Dort angekommen, stellten die Informatiker sofort fest, dass allgemeinere Eigenschaften behandelt werden müssen: Bedingte Gleichungen (auch als Horn-Gleichungssätze bezeichnet) und logische Eigenschaften erster Ordnung, die immer noch dieselben Ideen der universellen Algebra verwenden. Wie Sie bemerken würden, verschmilzt die Algebra nun mit der Modelltheorie.

Die Kategorietheorie ist die Grundlage für die Typentheorie. Da Informatiker immer wieder neue Strukturen erfinden, um mit verschiedenen Rechenphänomenen umzugehen, ist die Kategorietheorie ein sehr beruhigender Rahmen, in den all diese Ideen gestellt werden können. Wir verwenden auch Strukturen, die durch die Kategorietheorie ermöglicht werden und in der "traditionellen" Mathematik nicht existieren, wie z. B. Funktorkategorien. Auch die Algebra kehrt aus kategorialer Sicht in den Gebrauch von Monaden und algebraischen Effekttheorien zurück . Coalgebras , die Duale von Algebren, finden ebenfalls viel Anwendung.

Es gibt also eine weitreichende Anwendung von "Algebra" in der Informatik, aber es ist nicht die Art von Algebra, die in traditionellen Algebra-Lehrbüchern zu finden ist.

Zusätzliche Anmerkung : Es gibt einen konkreten Sinn, in welchem ​​Sinne Kategorietheorie Algebra ist. Monoid ist eine grundlegende Struktur in der Algebra. Es besteht aus einem binären "Multiplikations" -Operator, der assoziativ ist und eine Identität hat. Die Kategorietheorie verallgemeinert dies, indem den Elementen des Monoids "Typen" zugeordnet werden . Sie können „multiplizieren“ die Elemente nur dann , wenn die Typen entsprechen: wenn und dann . Zum Beispiel haben Matrizen eine Multiplikationsoperation, die sie zu einem Monoid macht. Allerdings Matrizen (wobei unda : X Y b : Y Z a b : X Z n × n m × n m na:XYa:XYb:YZab:XZn×nm×nmnkönnte unterschiedlich sein) bilden eine Kategorie. Monoide sind also Sonderfälle von Kategorien, die einen einzigen Typ haben. Ringe sind Sonderfälle von additiven Kategorien, die einen einzigen Typ haben. Module sind Sonderfälle von Funktoren, bei denen die Quell- und Zielkategorie einen einzigen Typ haben. Bald. Die Kategorietheorie ist eine typisierte Algebra, deren Typ sie unendlich anwendbarer macht als die traditionelle Algebra.

Uday Reddy
quelle
24
Kategorietheoretiker betrachten Algebra als Teil der Kategorietheorie. Algebraisten betrachten Kategorietheorie als Teil der Algebra. Logiker denken, sie sind beide verrückt.
Jeffs
4
Es gibt viele Wechselwirkungen zwischen Topologie und Algebra in der reinen Mathematik ...
Sasho Nikolov
16
Dies ist eine gute Antwort, aber ich denke, dass Ihre Kommentare zu "Reglementierung" und "Silokultur" irreführend sind. Der Grund, warum Algebra, Topologie und Logik für Sie einheitlich erscheinen, ist, dass die für Sie relevanten Teile dieser Themen für die Fragen, die Sie interessieren , sehr eng miteinander verflochten sind. Wenn Sie zum Beispiel versuchen würden, 4-dimensionale Mannigfaltigkeiten über die komplexen Zahlen zu klassifizieren, würden Sie schnell den Nutzen der traditionellen Unterscheidungen erkennen, die Mathematiker treffen. Es hängt alles davon ab, welches Problem Sie lösen möchten.
Timothy Chow
3
Ich persönlich bin immer noch völlig verblüfft über jede Schlussfolgerung, die Sie in Bezug auf die Forschungskultur in Mathematik und Informatik ziehen. Wie @TimothyChow hervorhebt, wurden verschiedene Unterfelder entwickelt, um verschiedene Arten von Problemen zu lösen, und daher wurden verschiedene Werkzeuge entwickelt. Wo es Sinn macht, Werkzeuge aus verschiedenen Teilbereichen mitzubringen, und die Leute das erkannt haben, gibt es Interaktion. Beispiele sollten nicht schwer zu finden sein, zum Beispiel in Vorlesungsskripten zur Lügenalgebra.
Sasho Nikolov
3
da es in der informatik weniger silokultur gibt, würde ich da auch anderer meinung sein. Ich persönlich habe keine Ahnung, warum PL-Forscher all diese schweren Maschinen brauchen, wofür sie sie verwenden, welches Problem sie damit lösen und warum es mich interessieren sollte. Vielleicht ist es meine eigene Ignoranz, aber ich bezweifle, dass die meisten Komplexitätstheoretiker und Algorithmiker die Antworten auf diese Fragen kennen ...
Sasho Nikolov
23

Meine Lieblingsanwendung der Gruppentheorie in TCS ist Barringtons Theorem. Sie können finden eine Ausstellung dieses Satzes von der Komplexität Blog , und Barrington Ausstellung im Kommentarbereich dieser Beitrag.

Dai Le
quelle
2
+1: und viele betrachten es als eines der überraschendsten Ergebnisse in der Komplexitätstheorie. :)
Kaveh
15

Gruppen, Ringe, Felder und Module befinden sich überall in der Computertopologie. Vgl. Insbesondere Carlssons und Zomorodians Arbeit [ex: 1 ] über (mehrdimensionale) persistente Homologie, bei der es um abgestufte Module über ideale Hauptdomänen geht.

Jeffε
quelle
@ JeffE, Links, bitte.
Scaaahu
1
@ JeffE, mein Kommentar sollte nicht anstößig sein. Ja, ich weiß, wie man googelt. Mein Punkt war, gibt es einen bestimmten Artikel von Carlsson und Zomorodian, der eine Art Überblick über persistente Homologie wäre? Wenn es eine gibt, lass es uns bitte wissen. Vielen Dank.
Scaaahu
Ich schlage vor, mit diesem Papier zu beginnen . (Entschuldigung, mein früherer Kommentar war nicht
erwünscht
@ JeffE, verstanden, genau das, wonach ich gesucht habe. Vielen Dank.
Scaaahu
14

Hier ist eine sehr schöne, praktische Anwendung: ein Algorithmus zur Berechnung der Konnektivität von Graphen (aus FOCS2011 ). Um die s-> t-Konnektivität eines Graphen zu berechnen, geben die Autoren einen Algorithmus an, der zufällige Vektoren mit Einträgen aus einem endlichen Feld den ausgehenden Kanten von s zuordnet und dann ähnliche Vektoren für alle Kanten im Graphen durch Zufallsgenerierung erstellt lineare Kombinationen, und schließlich entdecken Sie die Konnektivität durch Berechnen des Ranges der resultierenden Vektoren, die den In-Kanten von t zugewiesen sind.

Aaron Roth
quelle
Danke für den Hinweis und die Übersicht! Dies war vom FOCS 2011: dx.doi.org/10.1109/FOCS.2011.55
András Salamon
12

Gitter und Fixpunkte bilden die Grundlage für die Programmanalyse und -verifikation. Fortgeschrittene Ergebnisse aus der Gittertheorie werden jedoch selten verwendet, da wir uns mit algorithmischen Fragen wie dem Rechnen und der Approximation von Fixpunkten befassen, während die Forschung in der Gittertheorie einen anderen Schwerpunkt hat (Verbindungen zur Topologie, Dualitätstheorie usw.). Die anfänglichen abstrakten Interpretationspapiere verwenden die grundlegende Gittertheorie. Die Arbeit von Roberto Giacobazzi und seinen Mitarbeitern verwendet fortgeschrittenere Ergebnisse.

Beim verteilten Rechnen wurde eine berühmte Familie von Unmöglichkeitsergebnissen unter Verwendung von Methoden der algebraischen Topologie abgeleitet (siehe die Arbeit von Maurice Herlihy und Nir Shavit).

[Bearbeiten: Siehe Anwendungen der Topologie auf die Informatik .]

Vijay D
quelle
12

Die universelle Algebra ist ein wichtiges Instrument zur Untersuchung der Komplexität von Bedingungszufriedenheitsproblemen.

Zum Beispiel besagt die Dichotomie-Vermutung , dass grob gesagt ein Bedingungserfüllungsproblem über eine endliche Domäne entweder NP-vollständig oder polynomiell-zeitlich lösbar ist. Man beachte, dass es nach dem Ladner-Theorem Probleme in NP gibt, die nicht in P und nicht in NP-vollständig sind, es sei denn, P = NP, so dass die Vermutung besagt, dass CSPs speziell eine Dichotomie haben, die die größeren Komplexitätsklassen nicht haben. Es würde auch eine Erklärung liefern, warum die meisten Probleme, auf die wir in der Praxis stoßen, als NP-vollständig oder in P klassifiziert werden können.

Dichotomien wurden für verschiedene Sonderfälle nachgewiesen, z. B. binäre Domänen-CSPs (Schaefer) und ternäre Domänen-CSPs (Bulatov) sowie Homomorphismen in ungerichteten Graphen (Hell und Nesetril). Aber der allgemeine Fall ist ziemlich offen. Eine der Hauptangriffslinien ist die universelle Algebra. Sehr grob (und ich bin definitiv kein Experte in diesem Bereich!) Definiert man einen Polymorphismus von CSP als eine Funktion in der Domäne des CSP, die alle erfüllten Bedingungen erfüllt, wenn sie auf jede Variable angewendet werden. Die Menge der Polymorphismen eines CSP fängt in gewisser Weise seine Komplexität ein. Wenn beispielsweise ein CSP A alle Polymorphismen eines CSP B zulässt, ist A eine auf B reduzierbare Polynomzeit. Die Menge der Polymorphismen bildet eine Algebra, deren Struktur beim Entwerfen von Algorithmen / Anzeigen von Reduktionen hilfreich zu sein scheint. Wenn beispielsweise die Polymorphismusalgebra eines CSP idempotent ist und den unären Typ zulässt, ist der CSP NP-vollständig. Idempotenz ist eine vereinfachende Annahme, die mehr oder weniger ohne Verlust der Allgemeinheit gemacht werden kann. Das Zeigen, dass ein CSP, dessen Algebra idempotent ist und den unären Typ nicht zulässt, in der Polynomzeit gelöst werden kann, wird die Dichotomie-Vermutung beweisen.

Siehe die Umfrage von Bulatov: http://www.springerlink.com/content/a553847g6h673k05/ .

Sasho Nikolov
quelle
11

Hier sind zwei Anwendungen aus einem anderen Teil von TCS.

Semirings werden zur Modellierung von Annotationen in Datenbanken (insbesondere für Provenienzzwecke) und häufig auch für die Bewertungsstrukturen bei der Erfüllung von Valued Constraints verwendet. In diesen beiden Anwendungen müssen einzelne Werte auf eine Weise miteinander kombiniert werden, die auf natürliche Weise zu einer semirenden Struktur führt, wobei die Assoziativität und die eine semirende Operation über die andere verteilt sind. In Bezug auf Ihre Anfrage nach Modulen hat keines der beiden Monoide generell eine Inverse in diesen Anwendungen.

András Salamon
quelle
10

Ringe, Module und algebraische Varietäten werden zur Fehlerkorrektur und allgemeiner zur Codierungstheorie verwendet.

Insbesondere gibt es ein abstraktes Fehlerkorrekturschema (algebraische Geometriecodes), das Reed-Solomon-Codes und chinesische Restcodes verallgemeinert. Das Schema besteht im Grunde darin, Ihre Nachrichten von einem Ring R zu nehmen und zu codieren, indem Sie seine Reste modulo vieler verschiedener Ideale in R nehmen. Unter bestimmten Annahmen über R kann man beweisen, dass dies einen anständigen Fehlerkorrekturcode ergibt.

In der Welt der Liste der Decodierung ein kürzliches Papier von Guruswami gibt eine linear-algebraische Methode der Liste Decodierung Reed-Solomon - Codes gefaltet, die die schöne Eigenschaft hat , dass alle Kandidaten Nachrichten in einem niedrig-dimensionalen affinen Unterraum des Nachrichtenraumes liegen . Man kann ausweichende Unterraummengen konstruieren , Mengen, die fast so groß sind wie der gesamte Raum, aber einen kleinen Schnittpunkt mit jedem niedrigdimensionalen affinen Unterraum haben. Schränkt man Nachrichten ein, die von einem ausweichenden Unterraum innerhalb des Nachrichtenraums kommen, gibt Guruswamis Schema einen Algorithmus an, der eine schöne Listengröße garantiert. Bisher ist die einzige explizite Konstruktion Subraum Ausweich Sätze durch Dvir und Lovett in ihrem kommenden STOC Papier gegeben Subraum Evasive Sets und konstruiere die Menge, indem du eine bestimmte affine Sorte nimmst (und ihr kartesisches Produkt mitnimmst).

Alan Guo
quelle
6

Schauen Sie sich die Ramsey-Theorie an - im Grunde genommen eine bedeutende Verallgemeinerung des Pigeonhole-Prinzips , die vielen Automaten und der formalen Sprachtheorie zugrunde liegt (oder sollte ich sagen, das Pigeonhole-Prinzip ist der einfachste Fall der Ramsey-Theorie). Grundsätzlich heißt es, dass selbst hochgradig ungeordnete Strukturen, wenn sie groß genug sind, zwangsläufig eine Menge Ordnung enthalten. Beachten Sie für ein kleines Beispiel, das direkt hinter dem Pigeonhole-Prinzip liegt, dass sich drei Personen gegenseitig kennen oder drei von ihnen sich gegenseitig nicht kennen, wenn Sie sechs Personen nehmen.

Dieses Papier sieht aus wie ein guter Ausgangspunkt für Kontakte zur Informatik, aber Sie können nach weiteren Informationen suchen. Es ist in seiner grundlegenden Natur eher kombinatorisch als algebraisch, hat aber viele Anwendungen in der Algebra und im theoretischen CS.

Schauen Sie sich auch die Geschichte des Erfinders Frank Ramsey an - ein wahrhaft bemerkenswerter Polymath, der grundlegende, sogar revolutionäre Beiträge in den Bereichen Wirtschaft und Philosophie sowie Mathematik geleistet hat, von denen viele bis viel später unbeachtet blieben, bevor sie im Alter von 26 Jahren starben. denke nur! Tatsächlich war Ramseys ursprünglicher Satz, der die Grundlage der Ramsey-Theorie bildet, nur ein Deckmantel in einer Arbeit mit einem größeren Ziel in der mathematischen Logik.

David Lewis
quelle
2
Das ist klassisches Extremal-Kombinatorik-Zeug. Ich frage mich, wo siehst du den Zusammenhang mit Algebra? (Ich diskutiere nicht, dass Ramsey-Theorie eine Quelle großer Probleme und Theoreme ist)
Sasho Nikolov
Zum einen ist die Graphentheorie in der theoretischen CS extrem wichtig. Und sieh dir den Link in meiner Antwort sowie diese Suche an . Aus Pin, JE, Varieties of formal languages , Theorem 1.11 - Jede durch , erzeugte endliche Halbgruppe hat mit jedem Wort loinger als mit idempotentem mit , und all . Dies lässt sich am einfachsten mit Ramseys Theorem beweisen. A k > = 2 n w A + n e S w = x u 1 . . . u n y x , y A ˉ u i = eSAk>=2nwA+neSw=xu1...unyx,yAu¯i=e
David Lewis
Ich bestreite nicht die Relevanz der Ramsey-Theorie, geschweige denn der Graphentheorie für tcs. Ich sage, dass das OP nach Anwendungen der Algebra- und Ramsey-Theorie gefragt hat, was normalerweise nicht mit Algebra in Verbindung gebracht wird, afaik. Aber da Sie anscheinend eine gewisse Verbindung zwischen Ramsey-Theorie -> Algebra -> Tcs haben, können Sie dies vielleicht zu Ihrer Antwort hinzufügen
Sasho Nikolov
@Sasho - Wenn du meinst, dass Ramsey-Theorie kein Thema der Algebra ist, meine Antwort also falsch ist, dann bist du zu 100% richtig. Ich entschuldige mich für meine Antwort. Ich schätze, mein Verstand überschreitet leicht disziplinarische und subdisziplinäre Grenzen. Aber es ist schlimmer als das - Ramsey-Theorie ist in keiner Weise eine "algebraische Struktur". Bitte zögern Sie nicht, meine Antwort abzustimmen. Grüße.
David Lewis
Nun, während Downvoting vielleicht logisch wäre, liebe ich extreme Kombinatorik, also werde ich es nicht :) Übrigens bin ich mir ziemlich sicher, dass es einige Ramsey-artige Phänomene gibt, die bei algebraischen Strukturen auftreten, vielleicht sogar bei niedrigeren "Dichten" aufgrund der Symmetrien, also geben Sie mir eine Idee zu einer Frage
Sasho Nikolov
5

Die Analyse eines Problems mit viel Symmetrie wird durch die Verwendung der Gruppentheorie erleichtert. Ein Beispiel wäre, Algorithmen für Dinge wie Rubic's Cube zu finden. Obwohl ich die Details nicht kenne, bin ich sicher, dass der Nachweis, dass Gottes Zahl 20 ist , einige ernsthafte gruppentheoretische Kürzungen erfordert. In einem anderen Kontext verwenden praktische Löser für Graphisomorphismusprobleme wie Nauty die Automorphismusgruppe des Graphen.

Shitikanth
quelle
Auch die Algorithmen für den Graphisomorphismus [Luks '81; Babai - Luks '82] mit den bekanntesten Garantien (das heißt, sie funktionieren theoretisch, sind aber in der Praxis möglicherweise ineffizient) wenden die Gruppentheorie stark an und berufen sich sogar auf die Klassifizierung endlicher einfacher Gruppen.
Joshua Grochow
5

Algebra (und algebraische Geometrie) hat in der Kryptographie eine ziemlich große Rolle gespielt, mit elliptischen Kurvengruppen, (zahlentheoretischen) Gittern und natürlich als Grundlage für fast alle modernen kryptografischen Arbeiten.Zp

Pratyush Mishra
quelle
1
Soweit ich weiß, werden in der modernen Krypto-Technik andere algebraische Strukturen (endliche Felder, Ringe und andere Strukturen) verwendet. Dabei wird die Zahlentheorie allmählich aufgegeben und der Schwerpunkt liegt mehr auf Gittern, fehlerkorrigierenden Codes und "quantenresistenten" Problemen.
Josh
1

In der funktionalen Programmierung sind die allgemeinsten und elegantesten Abstraktionen für Probleme häufig algebraischer (oder kategorietheoretischer) Natur: Monoide, Semiringe , Funktoren, Monaden, F-Algebren, F-Kohlegebren usw. Einige klassische Ergebnisse (z. B. Yoneda) lemma) haben zufällig rechnerischen Inhalt und Nutzen.

Es gibt auch eine Homotopietypentheorie, die die Typentheorie in einer (Art) algebraischen topologischen Umgebung interpretiert.

xrq
quelle