Learning unions of tree patterns using queries

Authors: Hiroki Arimura, Hiroki Ishizaka, and Takeshi Shinohara.
Email: arim@i.kyushu-u.ac.jp

Source: Theoretical Computer Science Vol. 185, No. 1, 1997, 47-62.

Abstract. This paper investigates efficient learning of TP^k, 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 TP^k 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.