Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes

In this chapter, we consider classes of conventional decision tables closed relative to removal of attributes (columns) and changing decisions assigned to rows. For tables from an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum complexity of deterministic and nondeterministic decision trees and the complexity of deterministic and nondeterministic decision trees constructed by some algorithms on the complexity of the set of attributes attached to columns. We list all types of behavior of these functions. We also study the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that nondeterministic decision trees for a decision table can be interpreted as a way to represent an arbitrary system of true decision rules for this table that cover all rows.