Name
Title | ||
|---|---|---|
Polynomial Time Inductive Inference of Ordered Tree Patterns with Internal Structured Variables from Positive Data |
Abstract | ||
|---|---|---|
Tree structured data such as HTML/XML files are represented by rooted trees with ordered children and edge labels. As a representation of a tree structured pattern in such tree structured data, we propose an ordered tree pattern, called a term tree, which is a rooted tree pattern consisting of ordered children and internal structured variables. A term tree is a generalization of standard tree patterns representing first order terms in formal logic. For a set of edge labels 驴 and a term tree t, the term tree language of t, denoted by L驴(t), is the set of all labeled trees which are obtained from a term tree t by substituting arbitrary labeled trees for all variables in t. In this paper, we propose polynomial time algorithms for the following two problems for two fundamental classes of term trees. The membership problem is, given a term tree t and a tree T, to decide whether or not L驴(t) includes T. The minimal language problem is, given a set of labeled trees S, to find a term tree t such that L驴(t) is minimal among all term tree languages which contain all trees in S. Then, by using these two algorithms, we show that the two classes of term trees are polynomial time inductively inferable from positive data. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45435-7_12 | COLT |
Keywords | Field | DocType |
edge label,order term,internal structured variable,standard tree pattern,rooted tree,term tree,internal structured variables,rooted tree pattern,tree pattern,polynomial time inductive inference,ordered tree patterns,positive data,term tree language,inductive inference,first order,tree structure,formal logic,polynomial time | Range tree,K-ary tree,Artificial intelligence,Tree structure,(a,b)-tree,Interval tree,2–3 tree,Discrete mathematics,Combinatorics,Segment tree,Machine learning,Mathematics,Search tree | Conference |
ISBN | Citations | PageRank |
3-540-43836-X | 17 | 1.38 |
References | Authors | |
12 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yusuke Suzuki | 1 | 150 | 18.82 |
| Ryuta Akanuma | 2 | 17 | 1.38 |
| Takayoshi Shoudai | 3 | 269 | 31.89 |
| Tetsuhiro Miyahara | 4 | 267 | 32.75 |
| Tomoyuki Uchida | 5 | 255 | 35.06 |