This exercise concerns the expressiveness of
decision lists (Section learning-theory-section).
-
Show that decision lists can represent any Boolean function, if the size of the tests is not limited.
-
Show that if the tests can contain at most
$k$ literals each, then decision lists can represent any function that can be represented by a decision tree of depth$k$ .