Comparative Analysis of Deterministic and Nondeterministic Decision Trees for Decision Tables from Closed Classes

In this chapter, we investigate classes of decision tables with many-valued decisions closed under operations of removal of columns, changing of decisions, permutation of columns, and duplication of columns. We consider both general complexity measures and limited complexity measures including depth and weighted depth of decision trees. We study relationships among three parameters of these tables: the complexity of a decision table (if we consider the depth of decision trees, then the complexity of a decision table is the number of columns in it), the minimum complexity of a deterministic decision tree, and the minimum complexity of a nondeterministic decision tree. We consider rough classification of functions characterizing relationships and list all possible seven types of the relationships for general complexity measures and all possible five types of the relationships for limited complexity measures.