Learning of Ordered Tree Languages with Height-Bounded Variables Using Queries

摘要

We consider the polynomial time learnability of ordered tree patterns with internal structured variables, in the query learning model of Angluin (1988). An ordered tree pattern with internal structured variables, called a term tree, is a representation of a tree structured pattern in semistructured or tree structured data such as HTML/XML files. Standard variables in term trees can be substituted by an arbitrary tree of arbitrary height. In this paper, we introduce a new type of variables, which are called height-bounded variables. An i-height-bounded variable can be replaced with any tree of height at most i. By this type of variables, we can define tree structured patterns with rich structural features. We assume that there are at least two edge labels. We give a polynomial time algorithm for term trees with height-bounded variables using membership queries and one positive example. We also give hardness results which indicate that one positive example is necessary to learn term trees with height-bounded variables.