Comparison of Complexity of Regular versus Oblivious Decision Trees for Decision Tables with Many-valued Decisions from Closed Classes | Zendy

Azimkhon Ostonov | Zendy; Mikhail Moshkov | Zendy

Open Access

Comparison of Complexity of Regular versus Oblivious Decision Trees for Decision Tables with Many-valued Decisions from Closed Classes

Author(s) -

Azimkhon Ostonov,

Mikhail Moshkov

Publication year - 2025

Publication title -

ieee access

Language(s) - English

Resource type - Magazines

SCImago Journal Rank - 0.587

H-Index - 127

eISSN - 2169-3536

DOI - 10.1109/access.2025.3610956

Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation

In this work, we examine decision table (DTA) classes that are closed in terms of decision modification (i.e., the sets of decisions) and attribute deletion (i.e., columns). We examine the relationship between the minimum complexity of regular decision trees (DTRs) and the minimum complexity of oblivious DTRs, where the order of queries on attribute values is preset, for tables belonging to these classes. We show (and this is the main novelty of the paper) that the function expressing this dependence either grows logarithmically, or develops almost linearly, or is bounded from above by a constant. The depth and weighted depth of DTRs are examples of so-called bounded complexity measures (BCMs) for which this result is valid. Furthermore, for a DTA, we show that the minimum complexity of a reduct for that table is equal to the minimum complexity of an oblivious DTR.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research