Top-down Induction of Recursive Programs from Small Number of Sparse Examples

Basic representative set (BRS) is necessary for the induction of recursive concept using generalization under `-subsumption. To provide BRS, information is required about the target recursive theory which is yet to be learnt. Generalization method under inverse implication eliminates the strict necessity of the BRS, but is limited to learning very simple recursive programs. This paper proposes a new top-down approach implemented as a prototype system SMART, which learns fairly complex recursive programs from a small number of examples all lying on non-intersecting resolution path with respect to the target recursive theory. In addition, this paper illustrates some novel techniques for reducing the search complexities involved in logic program synthesis task