Completing open logic programs by constructive induction

We consider part of the problem of schema-biased inductive synthesis of rec ursive logic programs from incomplete specifications, such as clausal evide nce (for instance, but not necessarily, ground positive and negative exampl es). After synthesizing the base clause and introducing recursive call(s) t o the recursive clause, it remains to combine the overall result from the p artial results obtained through recursion, so as to complete the recursive clause. Evidence for this combination relation can be abduced from the init ially given evidence for the top-level relation. A program for this combina tion relation can be anything, from a single clause performing a unificatio n (such as for lastElem) to multiple guarded clauses performing unification s (such as for filtering programs) to recursive programs (such as for naive reverse). Existing methods cannot induce guarded clause programs far this combination relation from the abduced evidence. Some existing methods canno t even detect that the combination program itself may have to be recursive and thus they then do not recursively invoke themselves the overall recursi ve program synthesizer. We introduce our Program Completion Method as a sui table extension and generalization of the existing methods. (C) 1999 John W iley & Sons, Inc.