Die Algebra von allem

Linkverzeichnis

Zusammenfassung und 1 Einleitung

2 Grundlegende Definitionen und Notationen

2.1 Sätze

2.2 Sequenzen

2.3 Signaturen und Algebren und 2.4 Kategorien

3 Monographien und ihre Morphismen

4 Grenzwerte und Kogrenzwerte

5 Zeichenmonographien

6 Graphstrukturen und typisierte Monographien

7 Untermonographien und partielle Morphismen

8 Algebraische Transformationen von Monographien

9 typisierte Monographien mit Zuordnung

10 Schlussfolgerung und Referenzen

Abstrakt

Monographien sind graphenartige Strukturen mit gerichteten Kanten unbegrenzter Länge, die frei aneinandergrenzen. Die Standardknoten werden als Kanten der Länge Null dargestellt. Sie können in einer Weise gezeichnet werden, die mit Standardgraphen und vielen anderen, wie E-Graphen oder 8-Graphen, konsistent ist. Die Kategorie der Monographien hat viele Eigenschaften mit den Kategorien der Graphstrukturen (Algebren monadischer vielsortiger Signaturen) gemeinsam, außer dass es keine terminale Monographie gibt. Sie ist universell in dem Sinne, dass ihre Slice-Kategorien (oder Kategorien typisierter Monographien) den Kategorien der Graphstrukturen gleichwertig sind. Typische Monographien stellen somit eine natürliche Möglichkeit dar, Graphstrukturen zu spezifizieren. Es wird eine detaillierte Analyse von einfachen und doppelten Pushout-Transformationen von Monographien bereitgestellt, und ein Konzept attributierter typisierter Monographien, das typisierte attributierte E-Graphen verallgemeinert, wird im Hinblick auf attributerhaltende Transformationen analysiert.

Schlüsselwörter : Algebraische Graphtransformation, Graphstrukturen, typisierte Graphen

1 Einleitung

In der Mathematik und Informatik werden viele verschiedene Graphenbegriffe verwendet: einfache Graphen, gerichtete Graphen, Multigraphen, Hypergraphen usw. Ein beliebter Begriff im Zusammenhang mit Logik und Umschreiben ist der sogenannte Köcher, d. h. Strukturen der Form pN, E, s, tq, wobei N, E Mengen und s, t Funktionen von E (Kanten) nach N (Knoten) sind, die die Quell- und Zielspitzen jeder Kante (oder jedes Pfeils) identifizieren. Ein Grund dafür ist, dass die Kategorie der Köcher isomorph zur Kategorie der Algebren der vielsortierten Signatur mit zwei Sortierungen Knoten und Kanten und zwei Operatornamen src und tgt vom Typ Kanten Ñ Knoten ist. In Übereinstimmung mit dieser Tradition meinen wir in dieser Abhandlung mit Graphen durchgehend Köcher.

Um komplexe Datenstrukturen bequem darstellen zu können, ist es oft notwendig, die Struktur von Graphen mit Attributen anzureichern: Knoten oder Kanten können mit Elementen aus einer festen Menge beschriftet werden, mit Werten aus einer Algebra, mit Wertemengen wie in [1] usw. Ein interessantes Beispiel findet sich in [2] mit dem Konzept der E-Graphen, da die Attribute ebenfalls als Knoten betrachtet werden.

Genauer gesagt ist ein E-Graph eine Algebra, deren Signatur durch den folgenden Graphen dargestellt werden kann:

Die Namen der Sortierungen und Operatoren helfen, die Struktur von E-Graphen zu verstehen: Kanten verbinden die Knoten untereinander, NV-Kanten verbinden die Knoten mit den Werten und EV-Kanten verbinden die Kanten mit den Werten. Daher enthalten die Sortierungswerte Attribute, die ebenfalls Knoten sind. Wir sehen jedoch, dass in E-Graphen die EV-Kanten an Kanten angrenzen. Dies ist zwar kein Standard, aber wir können solche Strukturen dennoch als eine Art Graph akzeptieren, schon allein, weil wir verstehen, wie sie gezeichnet werden können.

Die Verallgemeinerung des Graphenbegriffs scheint also eine Verallgemeinerung der Signatur von Graphen als Algebren zu beinhalten. Diesen Weg beschreitet Michael L¨owe in [3], wo er eine Graphstruktur als monadische vielsortierte Signatur definiert. Tatsächlich haben in den obigen und vielen anderen Beispielen in [3] alle Operatoren die Stelligkeit 1 und können daher als Kanten von ihrer Definitionsdomäne zu ihrer Bereichssortierung betrachtet werden. Ist das der Grund, warum sie Graphstrukturen heißen? Das obige Beispiel zeigt jedoch, dass E-Graphen sich stark von dem Graphen unterscheiden, der ihre Signatur darstellt. Außerdem ist es nicht praktisch, unser Verständnis solcher Strukturen auf der Syntax zu basieren, d. h. auf den speziellen Namen, die den Sortierungen und Operatoren in der Signatur gegeben werden.

Darüber hinaus ist es schwer zu verstehen, wie die Algebren einiger sehr einfacher monadischer Signaturen als Graphen jeglicher Form interpretiert werden können. Nehmen wir beispielsweise die Signatur von Graphen und kehren wir die Zielfunktion zu tgt um: Knoten Ñ Kanten. Dann besteht eine Symmetrie zwischen den Sortierungen Knoten und Kanten, was bedeutet, dass in einer Algebra dieser Signatur Knoten und Kanten Objekte derselben Natur wären. Ist das noch ein Graph? Können wir ihn zeichnen? Schlimmer noch: Wenn die beiden Sortierungen zu einer zusammengefasst werden, bedeutet das, dass ein Knoten/eine Kante an sich selbst angrenzen kann?

Wir könnten diese Probleme lösen, indem wir Graphstrukturen auf eine Klasse monadischer Signaturen beschränken, deren Algebren sich garantiert orthodox verhalten, etwa durch klar getrennte Kanten und Knoten. Dies könnte jedoch der Willkür unterliegen und hätte einen weiteren Nachteil: Der Begriff der Graphstruktur führt nicht ohne Weiteres zu einer Kategorie. Tatsächlich ist es schwierig, Morphismen zwischen Algebren unterschiedlicher Signaturen zu definieren, schon allein, weil sie eine beliebige Anzahl von Trägermengen haben können.

Der hier gewählte Ansatz besteht vielmehr darin, jede strukturelle Unterscheidung zwischen Knoten und Kanten abzulehnen und somit eine einheitliche Sichtweise von Knoten als Kanten der Länge 0 und Standardkanten als Kanten der Länge 2 zu übernehmen, da sie an zwei Knoten angrenzen. Diese einheitliche Sichtweise lässt logischerweise zu, dass Kanten an beliebige Kanten und nicht nur an Knoten angrenzen, wodurch die E-Kanten von E-Graphen und sogar an Kanten, die an sich selbst angrenzen, verallgemeinert werden können. Schließlich gibt es keinen Grund, die Länge von Kanten auf 0 oder 2 zu beschränken, und wir werden (in Abschnitt 6) gute Gründe dafür finden, Kanten von unendlicher, ordinaler Länge zuzulassen. Die notwendigen Begriffe und Notationen werden in Abschnitt 2 eingeführt. Die Struktur der Monographie (zusammen mit Morphismen) wird in Abschnitt 3 definiert, woraus sich ein Bestiarium von Kategorien von Monographien entsprechend einiger ihrer Merkmale ergibt. Die Eigenschaften dieser Kategorien hinsichtlich der Existenz von Grenzwerten und Ko-Grenzwerten werden in Abschnitt 4 analysiert.

In Abschnitt 5 sehen wir dann, wie Monographien durch Zeichnungen präzise dargestellt werden können, vorausgesetzt natürlich, dass sie endlich viele Kanten und deren Länge endlich sind. Insbesondere entsprechen solche Zeichnungen der Standardzeichnung eines Graphen für Monographien, die mit Standardgraphen identifiziert werden können, und analog dazu für E-Graphen.

Abschnitt 6 widmet sich dem Vergleich zwischen Monographien und Graphstrukturen sowie den entsprechenden Algebren (die wir als graphstrukturierte Algebren bezeichnen können). Wir zeigen eine Eigenschaft der Universalität von Monographien in dem Sinne, dass alle graphstrukturierten Algebren (wenn auch meist nicht kanonisch) als typisierte Monographien, d. h. als Morphismen von Monographien, dargestellt werden können.

Der Begriff der Graphstruktur wurde in [3] eingeführt, um Kategorien partieller Homomorphismen zu erhalten, in denen Techniken der algebraischen Graphenumschreibung angewendet werden können. Die in Abschnitt 6 hergestellte Übereinstimmung mit Monographien erfordert eine ähnliche Entwicklung partieller Morphismen von Monographien in Abschnitt 7. Die einfachen und doppelten Pushout-Methoden zur Umschreibung von Monographien werden anschließend in Abschnitt 8 definiert, analysiert und verglichen.

Der Begriff des E-Graphs wurde in [2] eingeführt, um wohlgeformte Kategorien (bezüglich der Graphenumschreibung) von attributierten Graphen zu erhalten und somit geeignete Darstellungen realer Datenstrukturen vorzuschlagen. Dies wird erreicht, indem E-Graphs mit einer Datentypalgebra angereichert und Knoten mit Sortierungswert anhand der Elemente dieser Algebra identifiziert werden. Wir verfolgen in Abschnitt 9 einen ähnlichen Ansatz mit dem Begriff der attributierten typisierten Monographie, indem wir Elemente einer Algebra mit Kanten identifizieren und ähnlich wohlgeformte Kategorien erhalten. Aufgrund der Universalität von Monographien sehen wir, dass jede Σ-Algebra als attributierte typisierte Monographie dargestellt werden kann.

Wir schließen mit Abschnitt 10. Beachten Sie, dass Teile der Abschnitte 4 bis 6 in [4] veröffentlicht wurden.