RESEARCH NOTE ON DECISION LISTS

In his article ''Learning Decision Lists,'' Rivest proves that (k-DNF or k-CNF) is a proper subset of k-DL. The proof is based on the follow ing incorrect claim: ... if a function f has a prime implicant of size t, then f has no k-DNF representation if k < t. In this note, we show a counterexample to the claim and then prove a stronger theorem, from which Rivest's theorem follows as a corollary.