Department of Mathematical Cybernetics

The Department was established in 1970 by the Corresponding Member of the Russian Academy of Science (RAS) Sergey Yablonskiy who was the head of the Department till 1988. Academician of RAS Oleg Lupanov took part in the Department’s activity.

The main fields of scientific investigations are discrete mathematics and mathematical theory of control systems. Among the problems that attract Department’s attention there are combinatorial problems in graph theory, problems of expressibility for special classes of functional systems with operations, fast algorithms on discrete structures, some problems of the coding theory, cryptography and information security, problems of logics and logical program analysis. Methods for control systems’ synthesis that are developed at the Department are used for design of large scale integrated circuits.

Staff members:

• Voronenko Andrey, Professor, Dr.Sc.
• Lozhkin Sergey, Professor, Dr.Sc., Vice Dean for scientific work and finance
• Marchenko Alexander, Professor, Dr.Sc.
• Marchenkov Sergey, Professor, Dr.Sc.
• Podlovchenko Rimma, Professor, Dr.Sc.
• Sapozhenko Alexander, Professor, Dr.Sc.
• Zakharov Vladimir, Professor, Dr.Sc.,
• Romanov Dmitry, Associate Professor, PhD
• Selezneva Svetlana, Associate Professor, PhD, Scientific Secretary of the Department
• Shupletsov Mikhail, Assistant Professor, PhD, Acting Head of the Laboratory of Mathematical Problems of Computer Security
• Nagorny Alexander, Assistant Professor, PhD
• Bukhman Anton, Researcher, PhD
• Danilov Boris, Researcher
• Podymov Vladislav, Researcher
• Plaksina Anna, Laboratory Assistant

Regular courses:

• Discrete mathematics by Prof. Marchenkov, Prof. Alekseev, Assoc. Prof. Romanov, 48 lecture hours and 32 seminar hours, 2nd semester.
• Discrete mathematics by Prof. Voronenko, 36 lecture hours and 36 seminar hours, 1st semester.
• Discrete mathematics by Assoc. Prof. Selezneva, 32 lecture hours and 32 seminar hours, 2nd semesters.
• Selected topics in discrete mathematics by Prof. Marchenkov, 36 lecture hours and 36 seminar hours, 5th semester.
• Advanced topics in discrete mathematics by Assoc. Prof. Selezneva, 36 lecture hours, 5th semester.
• Elements of cybernetics by Prof. Sapozhenko and Prof. Lozhkin, 68 lecture hours and 36 seminar hours, 6th and 7th semesters; Prof. Lozhkin, 48 lecture hours, 6th semester; Prof. Voronenko, 36 lecture hours, 7th semester.
• Mathematical logic and logic programming by Prof. Zakharov, 48 lecture hours and 16 seminar hours, 6th semester.
• Mathematical logic and algorithm theory by Prof. Zakharov, 64 lecture hours and 32 seminar hours, 6th semester.
• Discrete models by Assoc. Prof. Selezneva, 16 lecture hours, 2nd semester (MSc).
• Functional systems by Prof. Marchenkov, 32 lecture hours, 8th semester.
• Selected topics in graph theory by Assoc. Prof. Romanov, 32 lecture hours, 6th semester.
• Algorithm complexity by Prof. Alekseev, 68 lecture hours, 7th semester.
• Equivalent transformations in computational models by Prof. Podlovchenko.
• Selected topics in mathematical theory of computing by Prof. Podlovchenko.

Special courses:

• Distributed algorithms by Prof. Zakharov.
• Elementary recursive functions by Prof. Marchenkov.
• Strong closure operators by Prof. Marchenkov.
• Partial Boolean functions by Prof. Marchenkov.
• Functional equations of multivalued logic by Prof. Marchenkov.
• Read-once functions and the decomposition method by Prof. Voronenko.
• Models of reconstructing discrete functions by Prof. Voronenko.
• Boolean functions’ minimization by Prof. Sapozhenko.
• Enumerating problems by Prof. Sapozhenko.
• Disjunctive normal forms by Prof. Sapozhenko.
• Boolean functions and polynomials by Assoc. Prof. Selezneva.
• Theory of reliability and circuit control; methods of test construction by Assoc. Prof. Romanov.
• Mathematical elements of functional programming by Prof. Podlovchenko.
• Structural implementation of discrete functions by Prof. Lozhkin.
• Additional chapters in cybernetics and control-system theory by Prof. Lozhkin.
• Mathematical problems in integrated circuit design by Prof. Lozhkin and Prof. Marchenko.
• Mathematical problems of planar and cell circuits by Prof. Lozhkin and Dr. Shupletsov.
• Mathematical methods and models of VLSI design by Prof. Marchenko.

Special scientific seminars:

• Discrete mathematics and mathematical cybernetics by Prof. Alekseev, Prof. Sapozhenko, Prof. Lozhkin.
• Discrete functions and algorithm complexity by Prof. Alekseev, Prof. Marchenkov, Prof. Voronenko.
• Discrete analysis by Prof. Sapozhenko.
• Theoretical problems of programming by Prof. Podlovchenko and Prof. Zakharov.
• Some problems of circuits’ synthesis by Prof. Lozhkin, Assoc. Prof. Romanov, Dr. Nagorny, Dr. Shupletsov.
• Synthesis and complexity of circuits; mathematical models of VLSI by Prof. Lozhkin, Prof. Marchenko, Assoc. Prof. Romanov, Dr. Shupletsov.
• Computational complexity of discrete problems by Assoc. Prof. Selezneva.

Main Scientific Directions:

Discrete models in problems of informatics

(Professors V.B. Alekseev, S.S. Marchenkov, A.A. Sapozhenko, A.A. Voronenko, Dr. S.N. Selezneva, and A.S. Nagorny)

Models based on Boolean, multiple-valued and automata functions are investigated. Related results can be used in such applications as the data processing storage and compression, information security, programming.

Discrete functions with different operations are investigated. Important results on the structure of lattices of closed classes in these functional systems are obtained. Several fragments of lattices are described.

Combinatorial and graph theory approaches to the problems of informatics are designed. Principal results are established on the number of combinatorial objects of special types. Among others are asymptotically exact bounds for the number of antichaines in unimodal partially ordered sets and for the number of sets free of sums.

Algebraic approach to the problems of informatics based on a polynomial representation of discrete functions is developed. New bounds are obtained for complexity of the representation of discrete functions by different polynomial forms.

Computational complexity

(Professors V.B. Alekseev, A.A. Voronenko, and Dr. S.N. Selezneva)

New fast algorithms for different problems are designed. Complexity of these problems is investigated. Results can be used in such applications as data processing, information security, programming.

Algebraic methods based on the idea of “model extension” for design of fast algorithms for combinatorial problems are worked out. By this idea, the fast algorithms are designed for recognition of properties of Boolean and multiple-valued functions given by vectors of values. An algorithm with almost linear complexity is designed for checking if Boolean or multiple-valued function is monotone. Complexity of algebraic problems is investigated in collaboration with Professor Markus Blaser (Germany). Complexity questions of the testing theory for Boolean functions are developed. Computational complexity of some problems (including the polynomial representations of discrete functions) is researched.

Complexity, synthesis and reliability of Boolean circuits and functions, mathematical models of VLSI design

(Professors S.A. Lozhkin, A.M. Marchenko, Dr. D.S. Romanov, M.S. Shupletsov)

Possibilities for applying theoretical scientific advances in the above-mentioned field to the problems of Electronic Design Automation (EDA) of modern Very Large Scale Integration (VLSI) circuits and, in particular, nano-scale VLSI circuits are investigated.

A significant part of the research in the field of circuit complexity and synthesis of VLSI circuits is based on an asymptotic approach which is traditional for the Russian school of mathematical cybernetics. In the framework of this approach the worst-case complexity is studied. The Department actively develops a new direction in this field which is associated with the development of synthesis methods. Application of these methods enabled to obtain high accuracy asymptotic bounds for the complexity of implementation of typical or hardest functions in different classes of discrete control systems. These bounds were established for a wide range of traditional models (Boolean circuits, Binary Decision Diagrams and etc.) and for some relatively new models such as networks of relations.

This research also led to a number of new results on the complexity of implementation of some application-specific Boolean functions, such as linear functions, multiplexors and etc. Problems of embedding circuits into different geometrical structures (such as rectangular lattices and grids, Boolean cubes and etc.) arise during the course of this research. The Department invests a significant effort into the development of effective methods for designing and optimization of such embedment.

In particular, significant results were obtained in the field of area complexity of VLSI circuits. These results are based on the investigation of cell circuits which model topology of the circuit in a simplified way. Furthermore, new results were acquired on the embedment of binary and ternary trees into rectangular lattice, the construction of systems of monochrome linking subtrees in Boolean cubes and etc.

The theory of reliability and control of VLSI circuits is an important and rapidly developing field of mathematical cybernetics. The Department’s research in this field is focused on the development of methods for designing tests of various types and acquisition of upper and lower bounds on the length (complexity) of these tests.

In course of this research a method of multi-partitions which enables to get "good" tests for periodic block circuits is proposed. Methods for constructing verification and diagnostic tests are developed for circuits with a possible local coalescence of a multiple number of inputs and etc.

The Department’s team participates in the research on mathematical problems of automation of synthesis of VLSI circuits. This study is carried out in collaboration with A.M. Marchenko, the head of the research division of the Nangate company (the world leader in the development of Electronic Design Automation (EDA) software for an automated design of nanometer range cell libraries), and representatives from a number of external academic and commercial organizations such as Intel and others.

The ongoing research is aimed at developing EDA tools and methods for the following tasks: logical and topological synthesis of VLSI circuits, automated creation of cell libraries, verification and etc. The above-mentioned tasks are considered to be computationally complex due to the fact that most of them are NP-complete. In order to solve these problems, different methods of the theory of algorithms, graph theory, computational geometry, linear, nonlinear and integer programming are applied.

Development and research in models of computation and techniques for the software verification

(Prof. R.I. Podlovchenko and Dr.Sc. V.A. Zakharov)

One of the major problems in mathematical cybernetics is the analysis of behavior of complex information systems such as microelectronic circuits, computer programs, net protocols, etc. In order to attack this problem, a wide variety of models and techniques from automata theory, graph theory, algebra, mathematical logics are invoked. These models and techniques are applied to the program verification, i.e. to check that all computations of a given information system conform to a given specification (requirements to the behavior of a system).

Our team contributed significantly to the research on this problem. We gave rise to a number of approaches to the solution of an equivalence checking problem and an equivalent transformation problem for computer programs, developed an algebraic theory of program schemes, and developed novel techniques of program verification. Our team collaborates with the Scientific Research Computing Center (MSU), the Laboratory of Computing Systems (MSU) and the Institute for System Programming in the research on verification of distributed and embedded systems, refactoring and optimization of programs, software obfuscation.

Recent publications:

• 2014

1. Bukhman A. V. Properties of polynomials of periodic functions and the complexity of periodicity detection by the Boolean function polynomial // Discrete Mathematics and Applications. 2014. 24. 3. P. 129-137.
2. Chemeritsky E.V., Smeliansky R.L., Zakharov V.A. A formal model and verification problems for Software Defined Networks // Automatic Control and Computer Sciences. 2014. 48. 7. P. 398-406.
3. Chistikov Dmitry, Fedorova Valentina, Voronenko Andrey Certificates of Non-Membership for Classes of Read-Once Functions // Fundamenta Informaticae. 2014. 132. 1. P. 63-77.
4. Konnov I.V., Podymov V.V., Volkanov D.Yu, Zorin D.A., Zakharov V.A. How to make a simple tool for verification of real-time systems // Automatic Control and Computer Sciences. 2014. 48. 7. P. 534-542.
5. Lozhkin S.A., Konovodov V.A. Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3 // Moscow University Mathematics Bulletin. 2014.69. 3. P. 100-105.
6. Marchenkov S.S. Functional equations for the functions of real variables // Moscow University Computational Mathematics and Cybernetics. 2014. 38. 1. P.21-26.
7. Marchenkov S.S. Positive closed classes of three-valued logic // Journal of Applied and Industrial Mathematics. 2014. 8. 2. P. 256-266.
8. Romanov Dmitry S. Method of synthesis of easily testable circuits admitting single fault detection tests of constant length // Discrete Mathematics and Applications. 2014. 24. 4. P. 227-251.
9. Selezneva S.N. On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts // Moscow University Computational Mathematics and Cybernetics. 2014. 38. 2. P. 64-68.
10. Selezneva Svetlana.N., Bukhman Anton V. Polynomial-Time Algorithms for Checking Some Properties of Boolean Functions Given by Polynomials // Theory of Computing Systems. 2014.
11. Shupletsov M.S., Golubeva L.I., Rubina S.S., Podvyaznikov D.A., Iwatani S., Mashko S.V. OpenFLUX2: 13 C-MFA modeling software package adjusted for the comprehensive analysis of single and parallel labeling experiments // Microbial Cell Factories. 2014. 13. 1:152.
12. Voronenko A. A new proof of Stetsenko’s theorem // Moscow univ. bull. Computational Mathematics and Cybernetics. 2014. 38. 2. P. 69-72.

• 2013

1. Alekseev V.B., Smirnov A.V. On the exact and approximate bilinear complexities of multiplication of 4x2 and 2x2 matrices // Proceedings of the Steklov Institute of Mathematics. 2013. 280. N 2. P. 100-116.
2. Fedorova V.S. On the complexity of the satisfiability problem for a system of functional Boolean equations // J. Appl. and Industrial Mathematics. 2013. 7. N 3. P. 344-354.
3. Lozhkin S.A., Danilov B.R. Delays of schemes in a model that considers the input values of functional elements // Moscow University Comput. Mathematics and Cybern. 2013. 37. N 3. P. 145-153.
4. Romanov D.S. Tests with respect to permutations of variables in Boolean functions // Computational Mathematics and Modeling. 2013. 24. N 4. P. 558-565.
5. Selezneva S.N. Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables // Computational Mathematics and Modeling. 2013. 24. N 1. P. 146-152.
6. Selezneva S.N. The circuit complexity of checking polynomiality for functions over a residue ring modulo a composite number is linear // Moscow University Comput. Mathematics and Cybern. 2013. 37. N 1. P. 21-25.
7. Voronenko A.A., Fedorova V.S. Generation of boolean functions under the assumption of monotonicity // Moscow University Comput. Mathematics and Cybern. 2013. 37. N 1. P. 26-27.

• 2012

1. Lozhkin S.A., Danilov B.R. Delay in networks of functional elements in a model with an arbitrary distribution of basis element input delays // Computational Mathematics and Modeling. 2012. 23. N 4. P. 487-506.
2. Marchenkov S.S. Atoms of the lattice of positive closed classes in three-valued logic // Discrete Mathematics and Applications. 2012. 22. N 2. P. 123-137.
3. Marchenkov S.S. Operator of positive closure // Doklady Mathematics. 2012. 85. N 1. P. 102-103.
4. Nagornii A.S. On the distribution of three-valued functions over pre-complete classes // Moscow University Comput. Mathematics and Cybern. 2012. 36. N 3. P. 155-163.
5. Romanov D.S. A method for synthesis of easily-testable circuits in some basis admitting single fault detection tests of constant length // Moscow University Mathematics Bulletin. 2012. 67. N 2. P. 69-73.
6. Romanov D.S. Diagnostic tests for local coalescences of variables in Boolean functions // Computational Mathematics and Modeling. 2012. 23. N 1. P. 72-79.
7. Voronenko A.A. On universal functions for the set of linear functions // Discrete Mathematics and Applications. 2012. 22. N 4. P. 421-425.
8. Larionov V.B., Fedorova V.S. Closed classes containing a homogeneous function class // Moscow University Comput. Mathematics and Cybern. 2012. 36. N 1. P. 36–40.
9. Chistikov D.V., Voronenko A.A., Zubkov O.V. An upper bound on checking test complexity for almost all cographs // Proc. 13th Intern. Symp. on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2011). Los Alamitos, California: IEEE Computer Society Press, 2012. P. 323-330.
10. Selezneva S.N. Constructing polynomials for functions over residue rings modulo a composite number in linear time // Proc. 7th Intern. Computer Science Symp. in Russia (CSR 2012). Lecture Notes in Computer Science. N 7353. Heidelberg: Springer, 2012. P. 303-312.
11. Voronenko A.A., Chistikov D.V., Fedorova V.S. Certificates of non-membership for classes of read-once functions // RuFiDim II. Proc. of the Second Russian Finnish Symp. on Discrete Mathematics. Turku, Finland: TUCS, 2012. P. 48-53.
12. Zakharov V.A., Podymov V.V., Zorin D.A., Volkanov D.Yu., Konnov I.V. On the designing of model checkers for real-time distributed systems // Third Workshop "Program Semantics, Specification, and Verification: Theory and Applications". Нижний Новгород: Изд-во Нижегородского ун-та, 2012. P. 72-81.