[Zurück]

E. Fokina:
"Algorithmic Properties of Equivalence Relations";
Betreuer/in(nen), Begutachter/in(nen): M. Baaz, M. Goldstern; Institut für Diskrete Mathematik und Geometrie, 2016; Rigorosum: 15.12.2016.

Äquivalenzrelationen formalisieren den Begri der Ähnlichkeit von mathematischen Objekten.
Aus Sicht der berechenbaren Strukturtheorie sind Äquivalenzrelationen ein nützliches Mittel,
um die E ektivität mathematischer Strukturen zu analysieren. Weiters ist die Untersuchung algorithmischer
Eigenschaften von Äquivalenzrelationen ein aktives Forschungsgebiet, das viele
o ene Fragen hat und die Aufmerksamkeit von Spezialisten auf sich zieht. Wir betrachten nur
abzählbare Strukturen in berechenbaren Sprachen. Wir setzen Strukturen mit ihren Atomardiagrammen
gleich. Insbesondere ist eine Struktur berechenbar, wenn ihr Atomardiagramm eine
berechenbare Teilmenge der natürlichen Zahlen ist. Wir betrachten die obengenannten Richtungen
zur Erforschung von Äquivalenzrelationen in berechenbarer Strukturtheorie.
Zuerst betrachten wir Isomorphismen beschränkten Turinggrades. Für einen Turinggrad d
sagen wir, dass eine berechenbare Struktur A d-kategorisch ist, falls es für jede isomorphe
Kopie B einen d-berechenbaren Isomorphismus zwischen A und B gibt. Wir untersuchen die
Beziehungen zwischen algebraischen, deskriptiven, und algorithmischen Eigenschaften mathematischer
Strukturen mit Hilfe der Begri e 0n
Kategorizität und relativer 0n
Kategorizität. Wir
betrachten natürliche Strukturklassen, inklusive verschiedener Arten von Gruppen, Booleschen
Algebras, Fraïssé Limits, usw. Diese Ergebnisse erscheinen als Teil des Papers "Computability-
Theoretic Categoricity and Scott Families" von E. Fokina, V. Harizanov und D. Turetsky.
Wir beantworten dann die Frage, wie schwierig es ist die Eigenschaft der e ektiven Kategorizität
für Strukturen mit verschiedenen algorithmischen Einschränkungen zu beschreiben.
Der Hauptbegri hier ist der Begri der Indexmenge. Wir geben die exakte Abschätzung der
Komplexität für die n-entscheidbare Strukturen, die kategorisch bezüglich m-entscheidbarer
Präsentationen sind, für verschiedene m; n 2 !. Die Ergebnisse erscheinen in "Index sets of
n-decidable structures categorical relative to m-decidable presentations" von E. Fokina, S. Goncharov,
V. Harizanov, O. Kudinov und D. Turetsky.
Schließlich verwenden wir Grade von Atomardiagrammen, um die inhärente Komplexität
iii
Kurzfassung der Dissertation
von Äquivalenzklassen verschiedener Strukturen zu charakterisieren. Wir führen den Begri
des Gradspektrums bezüglich n-Äquivalenz ein (zwei Strukturen sind n-äquivalent, falls ihre
n-Diagramme gleich sind). Die Ergebnisse stellen ein Teil des Papers "Degree Spectra of
Structures relative to Equivalence Relations" von E. Fokina, P. Semukhin und D. Turetsky dar.
Für alle Ergebnisse, die in dieser Dissertation enthalten sind, hat E. Fokina den Hauptbeitrag
geleistet, sowohl bei der Erbingung der Beweise als auch beim Verfassen der Publikationen.
Die Einführung enthält den Sto aus "Computable Model Theory" von E. Fokina, V. Harizanov
und A. Melnikov.