Learning of finite unions of tree patterns with internal structured variables from queries

摘要

We consider the polynomial time learnability of finite unions of ordered tree patterns with internal structured variables in the query learning model proposed by Angluin (1988). An ordered tree pattern with internal structured variables, called a term tree, is a rooted tree pattern which consists of tree structures with ordered children and internal structured variables. A term tree is suited for representing structural features in semistructured or tree structured data such as HTML/XML files. The language L(t) of a term tree t is the set of all trees which are obtained from t by substituting arbitrary trees for all variables in t. Moreover, for a finite set H of term trees, L(H) = ∪{sub}(t∈H)L(t). Our target of learning is a finite set H of term trees. We show that any finite union of languages defined by m term trees is exactly identifiable in polynomial time using at most 2mn{sup}2 restricted subset queries and at most m = 1 equivalence queries, where n is the maximum size of counterexamples.