COMPARITIVE ANALYSIS OF DETERMINISTIC AND NONDETERMINISTIC DECISION TREE COMPLEXITY. GLOBAL APPROACH
Mikhail Moshkov · Fundamenta Informaticae · 1996
We study the relationships between the complexity of a task description and the minimal complexity of deterministic and nondeterministic decision trees solving this task. We investigate decision trees assuming a global approach i.e. arbitrary checks from a given check system can be used for constructing decision trees.