Design and analysis of greedy algorithms for construction of decision and inhibitory trees, rules and tests. Development of extensions of dynamic programming approach for study of trees and rules (counting the number of optimal trees and rules, multi-stage optimization, construction of the set of Pareto optimal points, study of relationships between two cost functions and between cost and uncertainty). Applications to test optimization. Experimental study of trees and systems of rules as algorithms, as classifiers, and as ways for knowledge representation.​ ​

Development of mathematical and algorithmic foundations for extensions of dynamic programming approach for element-based trees over rectangular meshes (counting of the number of optimal trees, multi-stage optimization, construction of the set of Pareto optimal points, and study of relationships between two cost functions). Experimental study of meshes containing point and edge singularities.​

Development of mathematical and algorithmic foundations for extensions of dynamic programming approach for combinatorial optimization problems that allow usual dynamic programming approach (counting the number of optimal solutions, multi-stage optimization, construction of the set of Pareto optimal points, and study of relationships between two cost functions). Experimental study of known problems such as shortest paths in graphs, search trees, sequence alignment, matrix chain multiplication, etc.​

​Development of extensions of dynamic programming approach for study of (I) decision trees and rules (counting the number of optimal trees and rules, multi-stage optimization, construction of the set of Pareto optimal points, study of relationships between two cost functions and between cost and uncertainty) (II) element-based trees over rectangular meshes (counting of the number of optimal trees, multi-stage optimization, construction of the set of Pareto optimal points and study of relationships between two cost functions), (III) combinatorial optimization problems that allow usual dynamic programming approach (counting the number of optimal solutions, multi-stage optimization).Experimental study of various problems connected with decision trees, decision rules, and element-based trees.​ ​​ ​​​​

Generalization of results known for decision trees and rules over decision tables with many-valued decisions (bounds on complexity and greedy algorithms for construction) to the case of inhibitory trees and rules. Generalization of extensions of dynamic programming for decision trees and rules over decision tables with single-valued decisions to inhibitory trees and rules and to decision tables with many-valued decisions. Study of behavior of Shannon functions (describing relationships between complexity of problem description and complexity of problem solving) for decision and inhibitory trees and rule systems over decision tables with many-valued decisions.

Project of KAUST - Stanford AEA Program

Project of Russian Federal Program Scientific Research and Educational Workforce of Innovative Russia

Project of Russian Federal Program Research and Development in Prioritized Directions of Scientific-Technological Complex of Russia in 2007–2013 ​​​

Preparation of the book M. Moshkov, B. Zielosko, Combinatorial Machine Learning: A Rough Set Approach, Series Studies in Computational Intelligence, Vol. 360, 178 p., Springer, 2011

Preparation of the book I. Chikalov, Average Time Complexity of Decision Trees, Series Intelligent Systems Reference Library, Vol. 21, 104 p., Springer, 2011​

Initiative Project  ​