Inference of a minimum size boolean function from examples by using a new efficient branch-and-bound approach

This paper deals with the problem of identifying a hidden Boolean function : 0, 1' 0, 1 from positive and negative examples. This problem is of paramount importance in many real life applications of artificial intelligence. The method proposed in this paper is based on a branch-and-bound approach. This approach is an expansion of some earlier work (Triantaphyllouet al., 1994). Computational results, comparing the new method with one based on Karmakar's interior point method, suggest that the new method is very efficient.