Weighted Depth of Deterministic and Nondeterministic Decision Trees for Recognition Properties of Decision Rule Systems

Decision rule systems and decision trees are frequently used in computer science as interpretable models. Understanding their complexity in terms of attribute costs is crucial when decisions must be made with minimum resource usage. Our result shows a tight bound on how much more expensive a deterministic model can be, which can impact rule-based system design in cost-sensitive environments. This paper discusses various problems related to recognizing properties of decision rule systems using deterministic and nonde-terministic decision trees as solution algorithms. Importantly, a nondeterministic decision tree can be interpreted as a representation of a system of decision rules that are true for a given problem and cover all possible inputs. The paper shows that the minimum weighted depth of a deterministic decision tree solving a problem is bounded above by the square of the minimum weighted depth of a nondeterministic decision tree. This result, in particular, encourages consideration of the possibility of transforming decision rule systems into decision trees.