Ordered Term Tree Languages Which Are Polynomial Time Inductively Inferable from Positive Data

Abstract

In the fields of data mining and knowledge discovery, many semistructured data such as HTML/XML files are represented by rooted trees t such that all children of each internal vertex of t are ordered and t has edge labels. In order to represent structural features common to such semistructured data, we propose a regular term tree which is a rooted tree pattern consisting of ordered tree structures and internal structured variables. For a regular ordered term tree t , the term tree language of t , denoted by L(t) , is the set of all trees which are obtained from t by substituting arbitrary trees for all variables in t . In this paper, we consider a polynomial time learnability of the class OTTL = L(t) ∣ t ∈ OTT from positive data, where OTT denotes the set of all regular ordered term trees. First of all, we present a polynomial time algorithm for solving the minimal language problem for OTT which is, given a set of labeled trees S , to find a term tree t in OTT such that L(t) is minimal among all term tree languages which contain all trees in S . Moreover, by using this algorithm and the polynomial time algorithm for solving the membership problem for OTT in our previous work [ 15 ], we show that OTTL is polynomial time inductively inferable from positive data. This result is an extension of our previous results in [ 14 ].