@Article{Riv87b,
  author = 	 { Ronald L. Rivest },
  title = 	 { Learning Decision Lists },
  journal = 	 { Machine Learning },
  OPTyear = 	 { 1987 },
  OPTmonth = 	 { November },
  date =         { 1987-11 },                  
  volume = 	 { 2 },
  number = 	 { 3 },
  pages = 	 { 229--246 },
  publisher =    { Kluwer },                  
  doi =          { 10.1007/BF00058680 },                  
  abstract =     {
       This paper introduces a new representation for Boolean functions,
       called \emph{decision lists}, and shows that they are efficiently
       learnable from examples.  More precisely, this result is established
       for $k$-DL --- the set of decision lists with conjunctive clauses of
       size $k$ at each decision.  Since $k$-DL properly includes other well-known
       techniques for representing Boolean functions such as $k$-CNF (formulae
       in conjunctive normal form with at most $k$ literals per term), and 
       decisions trees of depth $k$, our result strictly increases the set
       of functions that are known to be polynomially learnable, in the
       sense of Valiant (1984).  Our proof is constructive: we present
       an algorithm that can efficiently construct an element of
       $k$-DL consistent with a given set of examples, if one exists.                  
                 },
}