Algebra Seminar talk
2007-10-12
Michael Pinsker
Angewandte Algebra 2: Redukte relationaler Strukturen, CSP, und lokale Klone
Abstract:
Ich schließe an den Vortrag Angewandte Algebra 1 von Martin
Goldstern im Juni an, setze aber kein Wissen über diesen voraus.
Gegeben sei eine relationale Struktur R (bestehend aus einer Grundmenge und Relationen auf dieser Menge). Es ist eine natürliche Frage der Modelltheorie, die Redukte von R zu bestimmen, also alle Einschränkungen von R auf weniger Relationen; dabei werden normalerweise zwei Redukte T, T' als äquivalent betrachtet, wenn sie einander mit first-order Formeln definieren können. Es gibt auch schwächere sinnvolle Äquivalenzbegriffe von Redukten: Beispielsweise kann man statt first-order Formeln nur primitiv positive Formeln (bestehend aus Konjunktionen und Existenzquantoren) erlauben. Äquivalenz bis auf primitiv positive Interdefinierbarkeit spielt eine wichtige Rolle, wenn man R als template eines CSP (Constraint Satisfaction Problems) auffaßt. Das durch R definierte CSP ist die Frage, wie kompliziert es ist, für eine gegebene endliche Struktur S zu bestimmen, ob ein Homomorphismus von S nach R existiert. Es ist bekannt, daß viele Komplexitätsprobleme der theoretischen Informatik sich als CSP formulieren lassen, und die Erforschung von CSP ist derzeit ein vielbeachtetes Thema der universellen Algebra.
Der relationalen Struktur R läßt sich in natürlicher Weise ein Klon zuordnen, nämlich die Menge Pol(R) aller Operationen auf der Grundmenge von R, die alle Relationen von R erhalten. Klone dieser Form heißen lokal abgeschlossen und bilden einen Verband L. Wir zeigen, wie das Verständnis der Struktur von L mit dem beschriebenen Problem der Modelltheorie zusammenhängt und diskutieren einige Eigenschaften von L.