@InProceedings{LMR88b,
  replaced-by =  { LMR91 },
  author = 	 { Nathan Linial and Yihshay Mansour and Ronald L. Rivest },
  title = 	 { Results on Learnability and the Vapnik-Chervonenkis dimension },
  pages = 	 { 120--129 },
  doi =          { 10.1109/SFCS.1988.21930 },                  
  booktitle =    { Proceedings of the Twenty-Ninth Annual Symposium on the Foundations of Computer Science },
  publisher =    { IEEE },
  date =         { 1988-10 },                  
  OPTyear = 	 { 1988 },
  OPTmonth = 	 { October 24--26, },
  OPTeditor = 	 {},
  eventtitle =   { FOCS'88 },
  eventdate =    { 1988-10-24/1988-10-26 },
  venue =        { White Plains, New York },
  keywords =     { Vapnik-Chervonenkis dimension, distribution-free model, dynamic sampling, finite
                   concept set, finite domain, learnability, learning systems },                  
  abstract =     { 
        The problem of learning a concept from examples in a distribution-free model
        is considered. The notion of dynamic sampling, wherein the number of examples examined
        can increase with the complexity of the target concept, is introduced. This method is used
        to establish the learnability of various concept classes with an infinite Vapnik-Chervonenkis
        (VC) dimension. An important variation on the problem of learning from examples, called approximating
        from examples, is also discussed. The problem of computing the VC dimension of a finite concept
        set defined on a finite domain is considered.                  
                 }
}