Ordered term tree languages which are polynomial time inductively inferable from positive data
Ordered term tree languages which are polynomial time inductively inferable from positive data
复制标题
DOI：
10.1016/j.tcs.2005.10.022
复制
发表时间：
2002-11
影响因子：
2.8
通讯作者：
Yusuke Suzuki;Takayoshi Shoudai;Tomoyuki Uchida;T. Miyahara
中科院分区：
文献类型：
--
作者：
Yusuke Suzuki;Takayoshi Shoudai;Tomoyuki Uchida;T. Miyahara
在数据挖掘和知识发现领域中，许多半结构化数据（如HTML/XML文件）都用根树t表示，使得t的每个内部顶点的所有子节点都是有序的，并且t具有边标签。为了表示这种半结构化数据的共同结构特征，我们提出了一个线性有序项树，这是一个有根树模式，由有序树结构和内部结构化变量与不同的变量标签。对于边标签集合Λ，设OTTΛ是所有线性有序项树的集合。对于OTTΛ中的线性有序项树t，t的项树语言，记为LΛ（t），是通过将任意有序树替换为t中的所有变量而从t获得的所有有序树的集合。给定一组有序树S，OTTL <$={L <$（t）<$t∈OTT <$}的最小语言问题是在OTT <$中找到一个线性有序项树t，使得L <$（t）在包含S中所有有序树的所有项树语言中是最小的.通过给出解决OTTLΛ最小语言问题的多项式时间算法，我们证明了OTTLΛ类是可以从正数据归纳推断的多项式时间。
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 linear ordered term tree, which is a rooted tree pattern consisting of ordered tree structures and internal structured variables with distinct variable labels. For a set of edge labels Λ, let OTTΛbe the set of all linear ordered term trees. For a linear ordered term tree t in OTTΛ, the term tree language of t, denoted by LΛ(t), is the set of all ordered trees obtained from t by substituting arbitrary ordered trees for all variables in t. Given a set of ordered trees S, the minimal language problem for OTTLΛ={LΛ(t)∣t∈OTTΛ} is to find a linear ordered term tree t in OTTΛsuch that LΛ(t) is minimal among all term tree languages which contain all ordered trees in S. We show that the class OTTLΛis polynomial time inductively inferable from positive data, by giving a polynomial time algorithm for solving the minimal language problem for OTTLΛ.