The Vapnik-Chervonenkis dimension of decision trees with bounded rank

Abstract.  We show that VCDIM(rDTn)=\sum_{i=0}^r {n \choose i }, where rDTn denotes the set of all boolean functions on n boolean variables defined by decision trees of rank at most r, and VCDIM(rDTn) denotes its Vapnik-Chervonenkis dimension. It follows that the number of examples needed for pac-learning rDTn can be determined modulo a small factor.