TITLE:
Closed Classes of Binary Complete Decision Tables with Many-Valued Decisions
AUTHORS:
Azimkhon Ostonov, Kerven Durdymyradov, Mikhail Moshkov
KEYWORDS:
Binary Complete Decision Table, Closed Class, Deterministic Decision Tree, Nondeterministic Decision Tree, Strongly Nondeterministic Decision Tree
JOURNAL NAME:
Journal of Intelligent Learning Systems and Applications,
Vol.17 No.4,
October
14,
2025
ABSTRACT: A binary complete decision table with many-valued decisions is a table with
n
attributes and
2
n
pairwise distinct rows filled with numbers from the set
{
0,1 }
. Each row of this table is labeled with a nonempty finite set of decisions. For a given row of the table, the task is to find a decision from the set of decisions attached to the row. Such tables are generalizations of Boolean functions. They can also be viewed as representations of various problems related to systems of decision rules. In this paper, we consider three types of classes of binary complete decision tables with many-valued decisions, closed with respect to removal of columns and changing of decisions. For tables from these classes, we study the relationships between the minimum weighted depth of deterministic, nondeterministic, and (for one type of classes) strongly nondeterministic decision trees and the total weight of attributes attached to columns. Note that nondeterministic decision trees and strongly nondeterministic decision trees for decision tables can be interpreted as a way of representing the two types of systems of decision rules for these tables.