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

Azimkhon Ostonov; Mikhail Moshkov

doi:10.1007/978-3-031-65665-1_11

On Complexity of 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 proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

Decision trees (DTRs) and decision rules are extensively examined and applied in various domains of computer science. The theory of DTRs and rules highlights several crucial inquiries, such as how the complexity of deterministic decision trees (DDTRs) and decision rule systems depends on the complexity of the set of attributes associated with the columns of the decision table (DT). In this research paper, we focus on the analysis of nondeterministic decision trees (NDTRs) as a substitute for decision rule systems. NDTRs can be seen as representations of decision rule systems. We examine classes of DTs featuring multi-valued decisions (known as multi-label DTs) that maintain closure under attribute removal (columns) and modifications to the sets of assigned decisions for rows. We examine the behavior of functions that describe the worst-case dependence of the minimum complexity of DDTRs and NDTRs on the complexity of the set of attributes associated with the columns of tables belonging to a closed class (CC) of DTs closed under the above two operations. We enumerate all possible types of behavior exhibited by these functions.

Original language	English (US)
Title of host publication	Rough Sets - International Joint Conference, IJCRS 2024, Proceedings
Editors	Mengjun Hu, Pawan Lingras, Chris Cornelis, Yan Zhang, Dominik Ślęzak, JingTao Yao
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	173-187
Number of pages	15
ISBN (Print)	9783031656644
DOIs	https://doi.org/10.1007/978-3-031-65665-1_11
State	Published - 2024
Event	International Joint Conference on Rough Sets, IJCRS 2024 - Halifax, Canada Duration: May 17 2024 → May 20 2024

Publication series

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

Conference

Conference	International Joint Conference on Rough Sets, IJCRS 2024
Country/Territory	Canada
City	Halifax
Period	05/17/24 → 05/20/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

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

Access to Document

10.1007/978-3-031-65665-1_11

Cite this

Ostonov, A., & Moshkov, M. (2024). On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. In M. Hu, P. Lingras, C. Cornelis, Y. Zhang, D. Ślęzak, & J. Yao (Eds.), Rough Sets - International Joint Conference, IJCRS 2024, Proceedings (pp. 173-187). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14839 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-65665-1_11

Ostonov, Azimkhon ; Moshkov, Mikhail. / On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. editor / Mengjun Hu ; Pawan Lingras ; Chris Cornelis ; Yan Zhang ; Dominik Ślęzak ; JingTao Yao. Springer Science and Business Media Deutschland GmbH, 2024. pp. 173-187 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{875937facc894d3ab0c20d206ea91f5b,

title = "On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes",

abstract = "Decision trees (DTRs) and decision rules are extensively examined and applied in various domains of computer science. The theory of DTRs and rules highlights several crucial inquiries, such as how the complexity of deterministic decision trees (DDTRs) and decision rule systems depends on the complexity of the set of attributes associated with the columns of the decision table (DT). In this research paper, we focus on the analysis of nondeterministic decision trees (NDTRs) as a substitute for decision rule systems. NDTRs can be seen as representations of decision rule systems. We examine classes of DTs featuring multi-valued decisions (known as multi-label DTs) that maintain closure under attribute removal (columns) and modifications to the sets of assigned decisions for rows. We examine the behavior of functions that describe the worst-case dependence of the minimum complexity of DDTRs and NDTRs on the complexity of the set of attributes associated with the columns of tables belonging to a closed class (CC) of DTs closed under the above two operations. We enumerate all possible types of behavior exhibited by these functions.",

keywords = "Closed classes of decision tables, Decision tables with many-valued decisions, Deterministic decision trees, Nondeterministic decision trees",

author = "Azimkhon Ostonov and Mikhail Moshkov",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; International Joint Conference on Rough Sets, IJCRS 2024 ; Conference date: 17-05-2024 Through 20-05-2024",

year = "2024",

doi = "10.1007/978-3-031-65665-1\_11",

language = "English (US)",

isbn = "9783031656644",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "173--187",

editor = "Mengjun Hu and Pawan Lingras and Chris Cornelis and Yan Zhang and Dominik {\'S}l{\c e}zak and JingTao Yao",

booktitle = "Rough Sets - International Joint Conference, IJCRS 2024, Proceedings",

address = "Germany",

}

Ostonov, A & Moshkov, M 2024, On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. in M Hu, P Lingras, C Cornelis, Y Zhang, D Ślęzak & J Yao (eds), Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14839 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 173-187, International Joint Conference on Rough Sets, IJCRS 2024, Halifax, Canada, 05/17/24. https://doi.org/10.1007/978-3-031-65665-1_11

On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. / Ostonov, Azimkhon ; Moshkov, Mikhail.
Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. ed. / Mengjun Hu; Pawan Lingras; Chris Cornelis; Yan Zhang; Dominik Ślęzak; JingTao Yao. Springer Science and Business Media Deutschland GmbH, 2024. p. 173-187 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14839 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes

AU - Ostonov, Azimkhon

AU - Moshkov, Mikhail

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024

Y1 - 2024

N2 - Decision trees (DTRs) and decision rules are extensively examined and applied in various domains of computer science. The theory of DTRs and rules highlights several crucial inquiries, such as how the complexity of deterministic decision trees (DDTRs) and decision rule systems depends on the complexity of the set of attributes associated with the columns of the decision table (DT). In this research paper, we focus on the analysis of nondeterministic decision trees (NDTRs) as a substitute for decision rule systems. NDTRs can be seen as representations of decision rule systems. We examine classes of DTs featuring multi-valued decisions (known as multi-label DTs) that maintain closure under attribute removal (columns) and modifications to the sets of assigned decisions for rows. We examine the behavior of functions that describe the worst-case dependence of the minimum complexity of DDTRs and NDTRs on the complexity of the set of attributes associated with the columns of tables belonging to a closed class (CC) of DTs closed under the above two operations. We enumerate all possible types of behavior exhibited by these functions.

AB - Decision trees (DTRs) and decision rules are extensively examined and applied in various domains of computer science. The theory of DTRs and rules highlights several crucial inquiries, such as how the complexity of deterministic decision trees (DDTRs) and decision rule systems depends on the complexity of the set of attributes associated with the columns of the decision table (DT). In this research paper, we focus on the analysis of nondeterministic decision trees (NDTRs) as a substitute for decision rule systems. NDTRs can be seen as representations of decision rule systems. We examine classes of DTs featuring multi-valued decisions (known as multi-label DTs) that maintain closure under attribute removal (columns) and modifications to the sets of assigned decisions for rows. We examine the behavior of functions that describe the worst-case dependence of the minimum complexity of DDTRs and NDTRs on the complexity of the set of attributes associated with the columns of tables belonging to a closed class (CC) of DTs closed under the above two operations. We enumerate all possible types of behavior exhibited by these functions.

KW - Closed classes of decision tables

KW - Decision tables with many-valued decisions

KW - Deterministic decision trees

KW - Nondeterministic decision trees

UR - http://www.scopus.com/inward/record.url?scp=85200677400&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-65665-1_11

DO - 10.1007/978-3-031-65665-1_11

M3 - Conference contribution

AN - SCOPUS:85200677400

SN - 9783031656644

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 173

EP - 187

BT - Rough Sets - International Joint Conference, IJCRS 2024, Proceedings

A2 - Hu, Mengjun

A2 - Lingras, Pawan

A2 - Cornelis, Chris

A2 - Zhang, Yan

A2 - Ślęzak, Dominik

A2 - Yao, JingTao

PB - Springer Science and Business Media Deutschland GmbH

T2 - International Joint Conference on Rough Sets, IJCRS 2024

Y2 - 17 May 2024 through 20 May 2024

ER -

Ostonov A , Moshkov M. On Complexity of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. In Hu M, Lingras P, Cornelis C, Zhang Y, Ślęzak D, Yao J, editors, Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 173-187. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-65665-1_11