  In this paper, we study arbitrary infinite binary information systems each of
which consists of an infinite set called universe and an infinite set of
two-valued functions (attributes) defined on the universe. We consider the
notion of a problem over information system, which is described by a finite
number of attributes and a mapping associating a decision to each tuple of
attribute values. As algorithms for problem solving, we investigate
deterministic and nondeterministic decision trees that use only attributes from
the problem description. Nondeterministic decision trees are representations of
decision rule systems that sometimes have less space complexity than the
original rule systems. As time and space complexity, we study the depth and the
number of nodes in the decision trees. In the worst case, with the growth of
the number of attributes in the problem description, (i) the minimum depth of
deterministic decision trees grows either as a logarithm or linearly, (ii) the
minimum depth of nondeterministic decision trees either is bounded from above
by a constant or grows linearly, (iii) the minimum number of nodes in
deterministic decision trees has either polynomial or exponential growth, and
(iv) the minimum number of nodes in nondeterministic decision trees has either
polynomial or exponential growth. Based on these results, we divide the set of
all infinite binary information systems into three complexity classes. This
allows us to identify nontrivial relationships between deterministic decision
trees and decision rules systems represented by nondeterministic decision
trees. For each class, we study issues related to time-space trade-off for
deterministic and nondeterministic decision trees.
