Efficient algorithms for modern information systems.
Efficient algorithms for modern information systems.
The relations of similarity verification are very useful in and testing of programs: they help to understand programs and to simplify their developments. Research experience and solutions to many problems of analysis programs (the equivalence checking programs, obfuscation and verification) shows that the quality and effectiveness of the algorithm for checking the similarity of programs can be significantly improved by applying deeper methods of semantic analysis of programs that use models and algorithms of algebra and the automata theory.
On the basis of the previously proposed algorithm of logic-thermal equivalence checking in the model of sequential imperative programs it was developed a polynomial-time algorithm for unification of programs, i.e. bringing two programs to the common form by choosing the appropriate initialization of the input variables.
Another problem of program analysis and transformation related to the field of reorganization (refactoring) programs has also been studied and solved. The aim of restructuring program due to equivalent transformations preserving the functional properties of the program is to bring it to a form that facilitates the understanding of the program, has a simple structure, smaller size, deprives excess structures and in particular facilitates the detection and elimination of the clones (collectively fragments of programs offering "similar" data conversion). Simplification of the code by replacing a number of fragments of the program by invocation of the same procedure or macro reduces the size of the program and facilitate its understanding and simplifies testing and analysis program, as homogeneous errors inherent in the fragments of the same clone can be detected and eliminated by analyzing the behavior of one procedure.
The project is implemented under the program of fundamental researches of Department of Mathematical Sciences of RAS "Algebraic and Combinatorial Methods of Mathematical Cybernetics and New Generation Information Systems".
