LEARNING UNIONS OF TREE PATTERNS USING QUERIES

This paper investigates efficient learning of TPk, the class of collec tions of at most k first-order terms, where each collection defines th e union of the sets of ground instances of each first-order term in th e collection. We present an algorithm that exactly learns every concep t in TPk in polynomial time in k and n using equivalence and membershi p queries, where n is the size of the longest counterexample given so far. We also show some lower bound results on the number of queries, a nd apply our result to learning restricted version of logic programs w hose computational mechanisms are only disjunctive definition and unif ication.