@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.
},
}