Decision trees and decision rule systems are widely used in different applications as algorithms for problem solving, as predictors, and as a way for knowledge representation. Reducts play key role in the problem of attribute (feature) selection.

The aims of this book are the consideration of the sets of decision trees, rules and reducts; study of relationships among these objects; design of algorithms for construction of trees, rules and reducts; and deduction of bounds on their complexity. We consider also applications for supervised machine learning, discrete optimization, analysis of acyclic programs, fault diagnosis and pattern recognition.

We study mainly time complexity in the worst case of decision trees and decision rule systems. We consider both decision tables with one-valued decisions and decision tables with many-valued decisions. We study both exact and approximate trees, rules and reducts. We investigate both finite and infinite sets of attributes.

This is a mixture of research monograph and lecture notes. It contains many unpublished results. However, proofs are carefully selected to be understandable. The results considered in this book can be useful for researchers in machine learning, data mining and knowledge discovery, especially for those who are working in rough set theory, test theory and logical analysis of data. The book can be used under the creation of courses for graduate students.