On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes

Azimkhon Ostonov*, Mikhail Moshkov

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In this paper, we consider classes of conventional decision tables closed relative to the removal of attributes (columns) and changing decisions assigned to rows. For tables from an arbitrary closed class, we study the dependence of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We also study the dependence of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that a nondeterministic decision tree can be interpreted as a set of true decision rules that covers all rows of the table.

Original languageEnglish (US)
Article number1411
JournalEntropy
Volume25
Issue number10
DOIs
StatePublished - Oct 2023

Bibliographical note

Publisher Copyright:
© 2023 by the authors.

Keywords

  • closed classes of decision tables
  • deterministic decision trees
  • nondeterministic decision trees

ASJC Scopus subject areas

  • Information Systems
  • Mathematical Physics
  • Physics and Astronomy (miscellaneous)
  • General Physics and Astronomy
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes'. Together they form a unique fingerprint.

Cite this