Positive preorders and computable reducibility on them as mathematical models of databases

Project type: Grant funding by the Science Committee of the Ministry of Education and Science of the RK

Code of the project: AP05131579 (01.01.2018 – 31.12.2020)

Title: Positive preorders and computable reducibility on them as mathematical models of databases.

The object of research, development or design: The structure of positive preorders with respect to computable reducibility.

Aim of work: The purpose of the project is to represent the preordered structures induced by positive preorders as mathematical models of databases; investigation of algebraic and algorithmic properties of the structure of degrees of positive preorders with respect to algorithmic reducibility; a description of the types of computable isomorphism of equivalent positive preorders; characterization of universal preorders for various classes of positive preorders; estimation an algorithmic complexity of some classes of positive preorders; various generalizations of the database model.

Research methods: The investigation on this project is of a theoretical nature, the results will mainly be presented as theorems with rigorous proofs for publication in scientific articles. To achieve the goal of our study, a broad arsenal of methods of the theory of computability, numbering theory, and the theory of constructive models are used. An important role in research will play Kleene’s recursion theorem and some of its generalizations, and the so-called “priority method” with finite and infinite injuries will be used to construct positive preorders.

Field of application: The proposed concepts of a mathematical database model can be useful to develop technologies for creating giant databases and to ensure the effectiveness of their work. The results of the research will be useful in the theory of constructive models for solving problems of the interpretability of  positively numbered models in another ones.

Project Investigator: Badaev S.A. (Al-Farabi Kazakh National University)

The organization – executor: IICT CS MES RK