Title: Berechenbare Transformationen von Strukturklassen
Other Titles: Computable Transformations of Classes of Structures
Language: English
Authors: Rossegger, Dino 
Qualification level: Diploma
Advisor: Fokina, Ekaterina  
Issue Date: 2015
Number of Pages: 47
Qualification level: Diploma
Abstract: 
Die Arbeit befasst sich mit berechenbaren Transformationen von Strukturklassen. Wir geben einen Überblick über die vorhandenen berechenbaren Transformationen und deren Relationen. Der Fokus liegt hier auf effektiver Bi-Interpretierbarkeit. Wir zeigen, dass die Klassen der Graphen und partiellen Ordnungen bi-interpretierbar sind und befassen uns mit einem neuen Resultat über die Äquivalenz der effektiven Bi-Interpretierbarkeit von Klassen und berechenbaren Funktoren. Weiters untersuchen wir zwei kürzlich erforschte berechenbarkeitstheoretische Eigenschaften von Strukturen, Theorie spektra und - n - spectra im Kontext der effektiven Bi-Interpretierbarkeit. Wir zeigen, dass jedes mögliche - 1 - und - 2 -Spektrum in den Klassen der partiellen Ordnungen und Graphen existiert.

The work reviews different notions of computable transformations on elementary classes of structures. We review the most prominent computable transformations, effective reducibility, computable embeddings, Turing computable embeddings, effective bi-interpretability and computable functors, discussing the different ideas behind them and their relations. Recent results on the equivalence of effective bi-interpretability and computable functors are discussed in detail and we prove that graphs and partial orders are effectively bi-interpretable and therefore share many computability theoretic properties such as degree spectra and computable dimension. At last the two recently examined notions of theory spectra and - n -spectra and their relation in context of computable transformations are examined. We show that any existing - 1 - and - 2 -spectrum can be found in the classes of graphs and partial orders.
Keywords: Berechenbarkeitstheorie; berechenbare Strukturen; berechenbare Transformationen
Computability theory; computable structures; effective transformations
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-82229
http://hdl.handle.net/20.500.12708/4103
Library ID: AC12685760
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

5
checked on Jun 23, 2021

Download(s)

62
checked on Jun 23, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.