Constructive Induction for Recursive Programs

Abstract

This paper presents an algorithm for inducing recursive first order Horn clause programs from examples without background knowledge. This algorithm invents new predicates and their definitions exhaustively until the instances of a new predicate become the same as examples except for the name of the predicate. Our system CIRP switches into constructive induction mode using a new heuristic taking advantage of the goal directed usefulness of incomplete clauses and of the fact that it is supplied with no background knowledge. It enables CIRP to avoid exhaustive search and to overcome some difficulties associated with employing encoding length principle as a switching element for constructive induction. This paper also describes a method for deciding the argument set for a new predicate by employing the structure of the arguments of the original predicate and reports the scope, limitation and remedy of limitation of this method.