We introduce a new representation class of Boolean functions - monotone ter
m decision lists which combines compact representation size with tractabili
ty of essential operations. We present many properties of the class which m
ake it an attractive alternative to traditional universal representation cl
asses such as DNF formulas or decision trees. We study the learnability of
monotone term decision lists in the exact model of equivalence and membersh
ip queries. We show that, for any constant k greater than or equal to 0, k-
term monotone decision lists are exactly and properly learnable with n(O(k)
) membership queries in n(O(k3)) time. We also show that n(Omega (k)) membe
rship queries are necessary for exact learning. In contrast, both k-term mo
notone decision lists (k greater than or equal to 2) and general monotone t
erm decision lists are not learnable with equivalence queries alone. We als
o show that a subclass of monotone term decision lists (disj-MDL) is learna
ble with equivalence and membership queries, while neither type of query al
one suffices, (C) 2001 Elsevier Science B.V. All rights reserved.