Comparison of Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-valued Decisions from Closed Classes

In this paper, we consider classes of decision tables with many-valued decisions closed relative to removal of attributes (columns) and changing sets of decisions assigned to rows. For tables from an arbitrary closed class, we study a function ${\mathcal{H}}_{\psi ,A}^{\mathrm{\infty }}(n)$ that characterizes the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that nondeterministic decision trees for a decision table can be interpreted as a way to represent an arbitrary system of true decision rules for this table that cover all rows. We indicate the condition for the function ${\mathcal{H}}_{\psi ,A}^{\mathrm{\infty }}(n)$ to be defined everywhere. If this function is everywhere defined, then it is either bounded from above by a constant or is greater than or equal to $n$ for infinitely many $n$. In particular, for any nondecreasing function $\phi$ such that $\phi (n)\ge n$ and $\phi (0)=0$, the function ${\mathcal{H}}_{\psi ,A}^{\mathrm{\infty }}(n)$ can grow between $\phi (n)$ and $\phi (n)+n$. We indicate also conditions for the function ${\mathcal{H}}_{\psi ,A}^{\mathrm{\infty }}(n)$ to be bounded from above by a polynomial on $n$.