Queries revisited Author: Dana Angluin Email: angluin@cs.yale.edu Source: Theoretical Computer Science Vol. 313, Issue 2, 17 February 2004, pp. 175-194. Abstract. We begin with a brief tutorial on the problem of learning a finite concept class over a finite domain using membership queries and/or equivalence queries. We then sketch general results on the number of queries needed to learn a class of concepts, focusing on the various notions of combinatorial dimension that have been employed, including the teaching dimension, the exclusion dimension, the extended teaching dimension, the fingerprint dimension, the sample exclusion dimension, the Vapnik-Chervonenkis dimension, the abstract identification dimension, and the general dimension.

©Copyright 2004 Elsevier Science B.V.