This exercise concerns the expressiveness of
decision lists (Section learning-theory-section).
1. Show that decision lists can represent any Boolean function, if the size of the tests is not limited.
2. 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$.
1. Show that decision lists can represent any Boolean function, if the size of the tests is not limited.
2. 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$.
This exercise concerns the expressiveness of
decision lists (Section learning-theory-section).
1. Show that decision lists can represent any Boolean function, if the
size of the tests is not limited.
2. 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$.