"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

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.

Key Words:
Boolean functions, CNF/DNF form, learning from examples, logical analysis, clause satisfiability problem, GRASP, randomized algorithms, inductive inference.

Download this paper as a PS (PostScript) file (size = 2,911 KB).

Download this paper as a PDF file (size = 2,500 KB).

Return to Dr. Triantaphyllou's Homepage.