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

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.