On Depth of Deterministic and Nondeterministic Decision Trees for Decision Rule Systems from Closed Classes

The study of the relationships between decision rule systems and decision trees is of considerable interest in computer science. These models are among the most interpretable tools used in knowledge representation, classification, and decision-making. In this paper, we consider classes of decision rule systems that are closed under the operations of attribute and rule removal. The motivation for this study is to understand how the structural properties of decision rule systems affect the complexity of decision trees constructed for solving the problems related to the system. For an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum depth of deterministic and nondeterministic decision trees that solve the problem of the existence of realizable rules in a decision rule system on the number of different attributes in this system. In particular, we consider the problem of deciding whether a realizable rule exists for a given tuple and analyze the worst-case tree depth required to solve this problem. We prove that these functions are either bounded from above by a constant or grow linearly. These results extend previous theoretical findings and may be useful for building efficient interpretable models in practice.