Expressive tests for classification and regression

We address the problem of computing various types of expressive tests for d ecision trees and regression trees. Using expressive tests is promising, be cause it may improve the prediction accuracy of trees, and it may also prov ide us some hints on scientific discovery. The drawback is that computing a n optimal test could be costly. We present a unified framework to approach this problem, and we revisit the design of efficient algorithms for computi ng important, special cases. We also prove that it is intractable to comput e an optimal conjunction or disjunction.