Polynomial Time Inductive Inference of Ordered Term Trees with Contractible Variables from Positive Data (New Aspects of Theoretical Computer Science)
Yusuke Suzuki, Takayoshi Shoudai, Satoshi Matsumoto, Tomoyuki Uchida, Tetsuhiro Miyahara · Institutional Repositories DataBase (IRDB) · 2003
Due to the rapid growth of Internet usage, tree structured data such as Web documents have been rapidly increasing.In order to analyze such tree structured data, efficient learning from tree structured data becomes more and more important.Tree structured data such as $\mathrm{H}\mathrm{T}\mathrm{M}\mathrm{L}/\mathrm{X}\mathrm{M}\mathrm{L}$ files are represented by rooted trees with ordered children and edge labels [1].In order to represent atree structured pattern common to such tree structured data, we proposed an ordered term tree, which is arooted tree with ordered children and structured variables [7].Avariable can be substituted by an arbitrary tree.An ordered term tree $t$ is said to be regular if all variable labels in $t$ are mutually distinct.Many tree structured data such as $\mathrm{H}\mathrm{T}\mathrm{M}\mathrm{L}/\mathrm{X}\mathrm{M}\mathrm{L}$ files have no rigid structure and have essential information in subtrees containing leaves.In order to deal with such tree structured data, we introduce anew tyPe of variable, called acontractible variable, which is regarded as an anonymous subtree in an ordered term tree and matches any subtree including asingleton vertex.Ausual variable, called an uncontractible variable, in aterm tree does not match asingleton vertex.The language of aregular ordered term tree $t$ is the set of all ordered trees which are obtained ffom $t$ by substituting ordered trees for variables in $t$ .The language of aregular ordered term tree $t$ shows the representing power of $t$ .Aleast generalized regular ordered term tree $t$ explaining given tree structured data $S$ is aterm tree $t$ whose language contains $S$ and is minimal.Consider the examples in Fig. 1.The term tree $t_{2}$ is aleast generalized regular ordered term tree for Ti, $T_{2}$ and $T_{3}$ .The ordered term tree $t_{1}$ also explains the three trees.But $t_{1}$ explains any tree with 2or more vertices.So $t_{1}$ is overgeneralized