  Decision trees and systems of decision rules are widely used as classifiers,
as a means for knowledge representation, and as algorithms. They are among the
most interpretable models for data analysis. The study of the relationships
between these two models 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 paper, 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 the given
input.

Artificial Intelligence;Computational Complexity