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

Azimkhon Ostonov; Mikhail Moshkov

doi:10.1007/978-981-97-5937-8_14

Depth 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

1 Scopus citations

Abstract

This paper examines types of decision tables with many-valued decisions that are closed under the attribute (columns) removal and changes in the sets of decisions assigned to rows. We analyze functions that describe the worst-case dependence between the minimum depth of deterministic and nondeterministic decision trees on the number of attributes for tables in any closed class. We list all types of various behaviors exhibited by these functions, including their joint behavior. It is worth noting that nondeterministic decision trees can be viewed as a means to represent any system of true decision rules for a given table that covers all rows.

Original language	English (US)
Title of host publication	Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings
Editors	Ngoc Thanh Nguyen, Krystian Wojtkiewicz, Richard Chbeir, Yannis Manolopoulos, Hamido Fujita, Tzung-Pei Hong, Le Minh Nguyen
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	164-174
Number of pages	11
ISBN (Print)	9789819759361
DOIs	https://doi.org/10.1007/978-981-97-5937-8_14
State	Published - 2024
Event	16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024 - Ras Al Khaimah, United Arab Emirates Duration: Apr 15 2024 → Apr 18 2024

Publication series

Name	Communications in Computer and Information Science
Volume	2144 CCIS
ISSN (Print)	1865-0929
ISSN (Electronic)	1865-0937

Conference

Conference	16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024
Country/Territory	United Arab Emirates
City	Ras Al Khaimah
Period	04/15/24 → 04/18/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

Keywords

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

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1007/978-981-97-5937-8_14

Cite this

Ostonov, A., & Moshkov, M. (2024). Depth of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. In N. T. Nguyen, K. Wojtkiewicz, R. Chbeir, Y. Manolopoulos, H. Fujita, T.-P. Hong, & L. M. Nguyen (Eds.), Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings (pp. 164-174). (Communications in Computer and Information Science; Vol. 2144 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-981-97-5937-8_14

Ostonov, Azimkhon ; Moshkov, Mikhail. / Depth of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. editor / Ngoc Thanh Nguyen ; Krystian Wojtkiewicz ; Richard Chbeir ; Yannis Manolopoulos ; Hamido Fujita ; Tzung-Pei Hong ; Le Minh Nguyen. Springer Science and Business Media Deutschland GmbH, 2024. pp. 164-174 (Communications in Computer and Information Science).

@inproceedings{a05f0829de1e466fb2ad92ffb6001f54,

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

abstract = "This paper examines types of decision tables with many-valued decisions that are closed under the attribute (columns) removal and changes in the sets of decisions assigned to rows. We analyze functions that describe the worst-case dependence between the minimum depth of deterministic and nondeterministic decision trees on the number of attributes for tables in any closed class. We list all types of various behaviors exhibited by these functions, including their joint behavior. It is worth noting that nondeterministic decision trees can be viewed as a means to represent any system of true decision rules for a given table that covers all rows.",

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 Singapore Pte Ltd. 2024.; 16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024 ; Conference date: 15-04-2024 Through 18-04-2024",

year = "2024",

doi = "10.1007/978-981-97-5937-8\_14",

language = "English (US)",

isbn = "9789819759361",

series = "Communications in Computer and Information Science",

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

pages = "164--174",

editor = "Nguyen, \{Ngoc Thanh\} and Krystian Wojtkiewicz and Richard Chbeir and Yannis Manolopoulos and Hamido Fujita and Tzung-Pei Hong and Nguyen, \{Le Minh\}",

booktitle = "Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings",

address = "Germany",

}

Ostonov, A & Moshkov, M 2024, Depth of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. in NT Nguyen, K Wojtkiewicz, R Chbeir, Y Manolopoulos, H Fujita, T-P Hong & LM Nguyen (eds), Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. Communications in Computer and Information Science, vol. 2144 CCIS, Springer Science and Business Media Deutschland GmbH, pp. 164-174, 16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024, Ras Al Khaimah, United Arab Emirates, 04/15/24. https://doi.org/10.1007/978-981-97-5937-8_14

Depth of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. / Ostonov, Azimkhon ; Moshkov, Mikhail.
Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. ed. / Ngoc Thanh Nguyen; Krystian Wojtkiewicz; Richard Chbeir; Yannis Manolopoulos; Hamido Fujita; Tzung-Pei Hong; Le Minh Nguyen. Springer Science and Business Media Deutschland GmbH, 2024. p. 164-174 (Communications in Computer and Information Science; Vol. 2144 CCIS).

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

TY - GEN

T1 - Depth 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 Singapore Pte Ltd. 2024.

PY - 2024

Y1 - 2024

N2 - This paper examines types of decision tables with many-valued decisions that are closed under the attribute (columns) removal and changes in the sets of decisions assigned to rows. We analyze functions that describe the worst-case dependence between the minimum depth of deterministic and nondeterministic decision trees on the number of attributes for tables in any closed class. We list all types of various behaviors exhibited by these functions, including their joint behavior. It is worth noting that nondeterministic decision trees can be viewed as a means to represent any system of true decision rules for a given table that covers all rows.

AB - This paper examines types of decision tables with many-valued decisions that are closed under the attribute (columns) removal and changes in the sets of decisions assigned to rows. We analyze functions that describe the worst-case dependence between the minimum depth of deterministic and nondeterministic decision trees on the number of attributes for tables in any closed class. We list all types of various behaviors exhibited by these functions, including their joint behavior. It is worth noting that nondeterministic decision trees can be viewed as a means to represent any system of true decision rules for a given table that covers all rows.

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=85201961377&partnerID=8YFLogxK

U2 - 10.1007/978-981-97-5937-8_14

DO - 10.1007/978-981-97-5937-8_14

M3 - Conference contribution

AN - SCOPUS:85201961377

SN - 9789819759361

T3 - Communications in Computer and Information Science

SP - 164

EP - 174

BT - Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings

A2 - Nguyen, Ngoc Thanh

A2 - Wojtkiewicz, Krystian

A2 - Chbeir, Richard

A2 - Manolopoulos, Yannis

A2 - Fujita, Hamido

A2 - Hong, Tzung-Pei

A2 - Nguyen, Le Minh

PB - Springer Science and Business Media Deutschland GmbH

T2 - 16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024

Y2 - 15 April 2024 through 18 April 2024

ER -

Ostonov A , Moshkov M. Depth of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. In Nguyen NT, Wojtkiewicz K, Chbeir R, Manolopoulos Y, Fujita H, Hong TP, Nguyen LM, editors, Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 164-174. (Communications in Computer and Information Science). doi: 10.1007/978-981-97-5937-8_14