Mikhail begun to write this book more than 30 years ago in Lobachevsky State University of Nizhni Novgorod, continued in University of Warsaw, University of Silesia in Katowice, and Stanford University, and finished last year in King Abdullah University of Science and Technology.
The aim of this book is to compare four parameters of problems over arbitrary information systems: complexity of problem representation and complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees for problem solving. Deterministic decision trees are widely used as classifiers, as a means of knowledge representation, and as algorithms. Nondeterministic (strongly nondeterministic) decision trees can be interpreted as systems of true decision rules that cover all objects (objects from one decision class).
This book develops tools for the study of decision trees, including bounds on complexity and algorithms for construction of decision trees for decision tables with many-valued decisions. It considers two approaches to the investigation of decision trees for problems over information systems: local, when decision trees can use only attributes from the problem representation, and global, when decision trees can use arbitrary attributes from the information system. For both approaches, all possible types of relationships among the considered four parameters are described and algorithmic problems of decision tree optimization are discussed.
The results presented are useful for researchers who apply decision trees and rules to algorithm design and to data analysis, especially those working in rough set theory, test theory, and logical analysis of data. This book can be used as the basis for graduate courses.
