Exact learning for infinite families of concepts
  In this paper, based on results of exact learning, test theory, and rough set
theory, we study arbitrary infinite families of concepts each of which consists
of an infinite set of elements and an infinite set of subsets of this set
called concepts. We consider the notion of a problem over a family of concepts
that is described by a finite number of elements: for a given concept, we
should recognize which of the elements under consideration belong to this
concept. As algorithms for problem solving, we consider decision trees of five
types: (i) using membership queries, (ii) using equivalence queries, (iii)
using both membership and equivalence queries, (iv) using proper equivalence
queries, and (v) using both membership and proper equivalence queries. As time
complexity, we study the depth of decision trees. In the worst case, with the
growth of the number of elements in the problem description, the minimum depth
of decision trees of the first type either grows as a logarithm or linearly,
and the minimum depth of decision trees of each of the other types either is
bounded from above by a constant or grows as a logarithm, or linearly. The
obtained results allow us to distinguish seven complexity classes of infinite
families of concepts.
