Construction of Decision Trees and Acyclic Decision Graphs from Decision Rule Systems

In this paper, we consider the problems of transforming systems of decision rules into decision trees. This paper builds upon our previous work [12]. In that paper, we showed that the minimum depth of a decision tree derived from the decision rule system can be much less than the number of different attributes in the rules from the system. In such cases, it is reasonable to use decision trees. In the present paper, for some types of decision rule systems and problems, we prove the existence of polynomial time algorithms for the construction of decision trees and two types of acyclic decision graphs representing decision trees. In all other cases, we prove the absence of such algorithms using the fact that the minimum number of nodes in decision trees or acyclic decision graphs can grow as a superpolynomial function depending on the size of decision rule systems. To avoid difficulties related to the number of nodes in the decision trees, we discuss also the possibility of not building the entire decision tree, but describing the computation path in this tree for the given input.