Ivannikov Institute for System Programming of the RAS

Modern algorithmic problems in discrete mathematics.

Start of project – 2014.

The problem of information security in cloud computing is much more complex than those of information security problems that are solved by known cryptographic means. In 2010, in the work of van Dyck et al. the mathematical model of cloud computing over sensitive data was presented. It is proved that in the case of two users data protection possible. There is a scientific problem of selection of models of cloud computing and computational tasks for which the protection of information is possible.

For the first time the problem of unification was investigated by J. Robinson in the development of the resolution method for systems of automatic theorem proving. In the future, the method of resolutions was the starting point for the development of the concept of logic programming and algorithms unification actually become the primary means of computing logic programs. Over the years, the task of unification has been studied in detail. It was found that the unification in addition to logic programming can be used in the development of automated theorem proving systems, text processing on natural and formal languages, the construction of systems term rewriting. A wide range of efficient algorithms for unification with almost linear complexity was developed, and also have been found suitable data structure for the practical implementation of these algorithms.

The concept of two-way unification was introduced by us for the first time. It is a natural evolution of the well-known concept of unification for logical expressions containing variables. The aim of our research is to evaluate the complexity of the task of unification bilateral programs.

The project is implemented under the Basic Research Program of Department of Mathematical Sciences of RAS "Modern Problems of Theoretical Mathematics".


Theoretical Computer Science

Go to the list of projects