Learning clauses by tracing derivations.

In this paper we present a systen able to learn logic programs by adopting an intesional evaluation of clauses. The induction procedure, called TRACY, works as follows. clauses from the hypothesis space are asserted in the knowledge base, and a derivation of each of the positive examples is attempted, while maintaining a trace of which clauses were used. When such a trace is found to cover a negative example, we backtrack to an alternative derivation. Finally, all traced clauses are put together to form the solution program.The method is proved to be correct and sufficient. The evaluation of the complexity of the approach is provided.