Algebraic structures and enumeration operators

a project supported by the Bulgarian Science Fund (Bilateral Projects 2016 - Bulgaria and Russia)

Project description

The goal of this project is to conduct research in Computability theory in two directions: Degree theory, Uniform reducibilities and Computable structure theory. The directions are selected based on previous accomplishments of the Sofia computability group and the group of Department of Algebra and Mathematical Logic, N. I. Lobachevsky, Institute of Mathematics and Mechanics, Kazan Federal University and a large collections of important problems that these accomplishments open up. The recent results by members of the Sofia computability group relate to previous work done by these experts. The collaboration between the two groups is therefore likely to be successful. The research is concentrated on two mathematical models for the problems that arise in natural sciences, compared to their information content. The rigidity issue of the more adequate model of the enumeration degrees is one of the main tasks in computability theory. It would reveal which problems can only be approximated and how accurately this can be done. It would allow transforming in an algorithmic way solutions of given problems into solutions of other problems. Thus, the question that arises is to what extent the local structure, consisting of the problems that we could approximate well, determines the entire structure of the information content of the problems. The hypothesis is that the local structure determines fully the global structure. A confirmation of this hypothesis would have significant consequences for computability theory.
The next step is to understand the objects at a higher level – the mathematical structures. To study the complexity of a structure, we associate with it a set of degrees that describes it: the spectrum of the structure. The task is to examine how the models of computability can be applied to the study of the effective properties of the classical mathematical objects. The complexity of the connections between the different presentations is also of interest, because it gives a more complete picture of the algorithmic properties of the structure. The Bulgarian project members form one of the strongest groups on computability theory in Europe, and the Kazan group is one of the strongest in the world. This project will consolidate this positive trend by providing the opportunity to work closely with some of the most prominent international experts in the field.

Participants

Bulgarian participants (Sofia University, Bulgaria)

• Hristo Ganchev
• Andrey Sariev
• Alexandra Soskova
• Mariya Soskova, also University of Wisconsin–Madison
• Stefan Vatev
• Alexander Terziivanov

Foreign participants (Kazan Federal University, Russian Federation)

• Iskander Kalimullin
• Marat Arslanov
• Andrey Frolov
• Marat Faizrahmanov
• Maksim Zubkov
• Mars Yamaleev
• Natalia Korneeva
• Ravil Bikmukhametov
• Damir Zainetdinopv
• Yana Mikhailovskaya

Published papers

1. Effective Embeddings for paris of structures, Nikolay Bazhenov, Hristo Ganchev, Stefan Vatev. Lecture Notes in Computer Science “Proceedings of CiE 2019”, vol. 11558 (2019), pp. 84 - 95 (doi) (preprint)
2. Computable embedding of classes of algebraic structures with congruence relation, Hristo Ganchev, Iskander Kalimullin, Stefan Vatev. Uchenye Zapiski Kazanskogo Universiteta, vol. 160, no. 4 (2018), pp. 731 - 737 (preprint)

Accepted papers

1. The automorphism group and definability of the jump operator in the ω-enumeration degrees, Hristo Ganchev and Andrey Sariev. to appear in Archive for Mathematical Logic (preprint)
2. A structural dichotomy in the enumeration degrees, Hristo Ganchev, Iskander Kalimullin, Joseph S. Miller, and Mariya I. Soskova. to appear in Journal of Symbolic Logic (doi) (preprint)

Submitted papers

1. Computable embeddings for pairs of linear orders, Nikolay Bazhenov, Hristo Ganchev, Stefan Vatev (preprint)