Monotone term decision lists

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.