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

The study of the relationships between deterministic decision trees and systems of decision rules can be seen as an important task of computer science. Methods for transforming decision trees into systems of decision rules are simple and well-known. In this chapter, we consider the inverse transformation problem, which is not trivial. We study the complexity of constructing decision trees and acyclic decision graphs representing decision trees from decision rule systems, and we discuss the possibility of not building the entire decision tree, but describing the computation path in this tree for a given input. We also consider dynamic programming algorithms that, for given decision rule systems, return the minimum depth of decision trees for these systems.