This paper describes the integration of a learning mechanism called complementary discrimination learning with a knowledge representation schema called decision lists. There are two main results of such an integration. One is an efficient representation for complementary concepts that is crucial for complementary discrimination style Iearning. The other is the first behaviorally incremental algorithm, called CDLZ, for learning decision lists. Theoretical analysis and experiments in several domains have shown that CDL2 is more efficient than many existing symbolic or neural network learning algorithms, and can learn multiple concepts from noisy and inconsistent data.