"A Greedy Randomized Adaptive Search Procedure (GRASP) for
Inferring Logical Clauses from Examples in Polynomial Time and
some Extensions"

Mathematical and Computer Modelling, Vol. 27, No. 1,
pp. 75-99, (1998).

A.S. Deshpande and E. Triantaphyllou

Abstract:
Two new heuristics are presented for inferring a small size
Boolean function from complete and incomplete examples in
polynomial time. These examples are vectors
defined in {1,0}^{n}
for the complete case, or in {1,0,*}^{n} for
the incomplete case
(where n is the number of binary attributes or atoms and "*"
indicates unknown value). Each example is either positive or
negative, if it must be accepted or rejected by the target
function, respectively. For the incomplete case, however, some
examples may be unclassifiable. Moreover, computational results
indicate that the proposed heuristics may also be effective in
solving very large problems with thousands of examples.