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 ...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.展开更多
基金supported by King Abdullah University of Science and Technology(KAUST).
文摘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.
