Learning unions of tree patterns using queries

AbstractThis paper investigates efficient learning of TPk, the class of collections of at most k first-order terms, where each collection defines the union of the sets of ground instances of each first-order term in the collection. We present an algorithm that exactly learns every concept in TPk in polynomial time in k and n using equivalence and membership 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, and apply our result to learning restricted version of logic programs whose computational mechanisms are only disjunctive definition and unification