Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs

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 transforming decision rule systems into decision trees and acyclic decision graphs representing decision trees. Based on the obtained results, we can formulate the next stage of research: instead of constructing the entire decision tree, we will study polynomial time algorithms that simulate the work of the decision tree on a given tuple of attribute values.