27 апреля (пятница) в 17 часов в 610 аудитории состоится семинар кафедры алгебры и математической логики.
Dino Rossegger (Institute of discrete mathematics and geometry, Vienna University of Technology) “Computable structure theory with respect to equivalence relations”
Degree spectra of structures and computable categoricity are two of the best studied notions in computable structure theory. The aim of the two notions is to answer the following questions:
1. Which families of Turing degrees can be realized as degrees of isomorphic copies of a structure?
2. Given a computable structure, how hard is it to compute isomorphism between it and other computable copies?
In my research I studied these questions with respect to other equivalence relations than isomorphism: How hard is it to compute embeddings between bi-embeddable computable structures? And which families of degrees are realized by bi-embeddable or elementary bi-embeddable copies of a structures?
In my talk I will discuss these questions and present additional results on Scott sentences of linear orderings and computable transformations of classes of structures.