Algebraische Zugänge zur Beschreibung von Mal´cev-Klonen

Die Disziplin Algebra hat sich ursprünglich mit dem Lösen von Gleichungen beschäftigt. Um die Lösbarkeit von Gleichungen zu beschreiben, rechneten N.H.Abel (1802-1829) und É.Galois (1811-1832) mit anderen Objekten als mit Zahlen: sie fassten Vertauschungen von Lösungen zu Gruppen zusammen. Heute ist die Algebra das Gebiet, in dem studiert wird, wie man mit beliebigen mathematischen Objekten, etwa mit solchen Vertauschungen, mit Zahlen, mit Kurven in der Ebene, mit Dateien in einem Computerspeicher, oder mit Hierarchien innerhalb einer Gruppe von Personen rechnen kann. Sehr oft ist die Anzahl der Objekte, mit denen man rechnen will, endlich. Ziel dieses Forschungsvorhabens ist es, diese endlichen algebraischen Strukturen zu charakterisieren. Dabei verstehen wir zwei algebraische Strukturen als gleich, wenn sich die Rechenoperationen der einen durch die Operationen der anderen ausdrücken lassen, was in technischen Termini heißt, dass sie den gleichen "Klon von Termfunktionen" besitzen. Seit etwa 25 Jahren weiß man, dass es zu viele verschiedene endliche algebraische Strukturen gibt, als dass sich jede durch endlich viel Information darstellen ließe. Viele der natürlich auftretenden algebraischen Strukturen haben aber eine Zusatzeigenschaft: sie sind sogenannte Mal`cev-Algebren (benannt nach dem russischen Mathematiker A.I.Mal`cev (1909-1967)). Es war bis vor kurzem ein offenes Problem, ob sich jede endliche Mal`cev-Algebra, auch wenn sie unendlich viele Rechenoperationen besitzt, durch endlich viel Information, also etwa in einer Computerdatei, darstellen lässt. Seit 2009 weiß man, dass sich jede endliche Mal`cev-Algebra durch endlich viele Eigenschaften ihrer Operationen vollständig beschreiben lässt. Das Unangenehme dabei: diese endliche Darstellung existiert zwar sicher, man weiß aber noch nicht, wie sie aussieht, und wie man sie finden kann. Das zu klären ist eines der Ziele dieses Vorhabens. Dazu stehen Methoden aus dem Gebiet der universellen Algebra zur Verfügung, etwa die Theorie der Funktionenalgebren (auch "Klone" genannt) die Theorie der Polynominterpolation auf algebraischen Strukturen, oder die höheren Kommutatoren universeller Algebren. Im vorliegenden Antrag haben wir einige Probleme herausgearbeitet, deren Lösung die Beschreibung endlicher Mal`cev-Klone weiterbringen würde: es sollen höhere Kommutatoren weiterentwickelt und besser beschrieben, sowie ihr Zusammenhang mit den Polynomfunktionen einer Algebra besser geklärt werden, neue Vollständigkeitsbegriffe sollen definiert und untersucht, und die Übersetzung zwischen funktionaler und relationaler Beschreibung von Klonen untersucht und gegebenfalls ermöglicht werden, und schließlich soll die relationale Seite von Mal`cev-Klonen genauer untersucht werden.

Ziel dieses Projekts war, mithilfe klassischer und moderner algebraischer Strukturtheorie, die rechnerische Ausdrucksfähigkeit einer Algebra, die in ihren Termfunktionen steckt, zu untersuchen. Das Zusammenspiel von klassischer und universeller Algebra hat neue Resultate in der Gleichungslogik, der Kommutatortheorie, der algebraischen Interpolations- und Strukturtheorie und der Theorie der Funktionenalgebren und Klone geliefert.Aus Sicht des Projektleiters war eine neue Anwendung klontheoretischer Methoden auf die Gleichungslogik einer der größten Fortschritte in diesem Projekt. Das Ausmaß des Nichtzutreffens einer Gleichheit wie z.B. x+y=y+x wurde dazu in eine Funktion auf der Algebra kodiert. Durch Vergleich der möglichen Ausmaße konnte ein Problem in der Gleichungslogik, das explizit unter den großen offenen Problemen der universellen Algebra angeführt war, für große Klassen von Algebren gelöst werden.Das direkte Produkt zweier Algebren ist eine neue Struktur, in der man in bei- den Algebren parallel rechnet. Es ist interessant, wie sich diese beiden Faktoren im Produkt gegenseitig beeinflussen. Wir haben einen effizienten Test entwickelt, festzustellen, ob die beiden Algebren unabhängig sind, also keinen Einfluss aufeinander haben.Bestimmte Funktionen auf algebraischen Strukturen lassen sich durch gutartige Funktionen, sogenannte Polynomfunktionen, interpolieren. Schon lange beschäftigt man sich damit, jene Strukturen zu charakterisieren, in denen jede kongruenzerhaltende Funktion eine Polynomfunktion ist. Die Klassifikation aller Gruppen der Ordnung ? 100 hinsichtlich dieser Eigenschaft wurdeabgeschlossen.Die Theorie höherer Kommutatoren, ein Teilbereich universell algebraischer Strukturtheorie, wurde in zwei Aufsätzen vorangetrieben: eine Arbeit beschränkt die Anzahl der möglichen Kommutatoroperationen auf einer endlichen Algebra, die andere beschreibt Kommutatoren durch Erhaltungseigenschaften der Termfunktionen. In weiteren Arbeiten wurde die Strukturtheorie nilpotenter Algebren erweitert.Für jede algebraische Struktur trägt ihr Klon der Termfunktionen entscheidende Eigenschaften dieser Struktur. Dieser Klon kann nicht immer durch endlich viel Information dargestellt werden. Einige neue Resultate zeigen, wann sich Klone endlich darstellen lassen. Die Sprache der Klontheorie wurde erweitert, um auch bestimmte logische Gatter, die in der Theorie der reversiblen Berechnungen auftreten, fassen zu können. Es wurde gezeigt, wie sich beliebige Gatter durch spezielle Gatter, sogenannte Toffoli-Gatter zusammenbauen lassen.