Three Problems for Decision Rule Systems from Closed Classes

The study of the relationships between DRSs (Decision Rule Systems) and DTs (Decision Trees) is of considerable interest in computer science. In this paper, we consider classes of DRSs that are closed under specific operations. First, we examine classes that are closed under the operation of the removal of features and analyze the functions characterizing the worst-case dependence of the minimum depth of DDTs (Deterministic Decision Trees) and NDTs (Nondeterministic Decision Trees), solving the task of finding all true DRs in a DRS on the number of different features in the system. Second, we extend our analysis to classes that are closed under the removal of features and rules, studying the worst-case behavior of the minimum DT depth for the task of finding at least one true DR. Third, we investigate classes closed under the removal of features and rules in the context of finding all right-hand sides of true DRs. We prove that, in all three cases, the corresponding functions characterizing the worst-case minimum depth of DTs are either bounded from above by a constant or grow linearly.