Bounds on Depth of Decision Trees Derived from Decision Rule Systems

The study of relationships between systems of decision rules and deterministic decision trees is an important task of computer science. It is easy to transform a decision tree into a decision rule system. The inverse transformation is a more difficult task. In this chapter, we study unimprovable upper and lower bounds on the minimum depth of decision trees derived from decision rule systems depending on the various parameters of these systems. To illustrate the process of transformation of decision rule systems into decision trees, we generalize a well known result for Boolean functions to the case of functions of k-valued logic.