Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes

Azimkhon Ostonov*, Mikhail Moshkov

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Decision rules and decision trees are studied intensively in rough set theory. The following questions seem to be important for this theory: relations between decision trees and decision rule systems, and dependence of the complexity of decision trees and decision rule systems on the complexity of the set of attributes attached to columns of the decision table. In this paper, instead of decision rule systems we study nondeterministic decision trees that can be considered as representations of decision rule systems. We consider classes of decision tables with many-valued decisions (multi-label decision tables) closed relative to removal of attributes (columns) and changing sets of decisions assigned to rows. For tables from an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We enumerate all types of behavior of these functions. We also study the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. This study leads to understanding of the nontrivial relationships between deterministic decision trees and systems of decision rules represented by nondeterministic decision trees.

Original languageEnglish (US)
Title of host publicationRough Sets - International Joint Conference, IJCRS 2023, Proceedings
EditorsAndrea Campagner, Oliver Urs Lenz, Shuyin Xia, Dominik Ślęzak, Jarosław Wąs, JingTao Yao
PublisherSpringer Science and Business Media Deutschland GmbH
Pages89-104
Number of pages16
ISBN (Print)9783031509582
DOIs
StatePublished - 2023
EventInternational Joint Conference on Rough Sets, IJCRS 2023 - Krakow, Poland
Duration: Oct 5 2023Oct 8 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14481 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Joint Conference on Rough Sets, IJCRS 2023
Country/TerritoryPoland
CityKrakow
Period10/5/2310/8/23

Keywords

  • Closed classes of decision tables
  • Decision tables with many-valued decisions
  • Deterministic decision trees
  • Nondeterministic decision trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes'. Together they form a unique fingerprint.

Cite this