Efficient Learning of Semi-structured Data from Queries
Efficient Learning of Semi-structured Data from Queries
复制标题
从查询中高效学习半结构化数据
DOI：
10.1007/3-540-45583-3_24
复制
发表时间：
2001
影响因子：
3.8
通讯作者：
S. Arikawa
中科院分区：
文献类型：
--
作者：
Hiroki Arimura;H. Sakamoto;S. Arikawa
研究了Angluin查询学习模型中的有序间隔树模式（OGT）和有序间隔森林（OGF）类在入匹配语义下的多项式时间可学习性。OGT类是半结构化数据库查询语言的模型，是有序/无序树模式语言类和非擦除正则模式语言类的推广。首先，我们提出了一个多项式时间学习算法的μ-OGT，没有重复的树变量的OGT的子类，使用等价查询和成员查询。通过对该算法的扩展，利用等价查询和子集查询分别给出了无重复变量森林类的μ-OGF和有重复变量树类的OGT的多项式时间学习算法.我们还给出了独立于表示的硬度结果，表明等价查询和隶属查询都是学习μ-OGT所必需的。
This paper studies the polynomial-time learnability of the classes of ordered gapped tree patterns (OGT) and ordered gapped forests (OGF) under the into-matching semantics in the query learning model of Angluin. The class OGT is a model of semi-structured database query languages, and a generalization of both the class of ordered/unordered tree pattern languages and the class of non-erasing regular pattern languages. First, we present a polynomial time learning algorithm for µ-OGT, the subclass of OGT without repeated tree variables, using equivalence queries and membership queries. By extending this algorithm, we present polynomial time learning algorithms for the classes µ-OGF of forests without repeated variables and OGT of trees with repeated variables using equivalence queries and subset queries. We also give representation-independent hardness results which indicate that both of equivalence and membership queries are necessary to learn µ-OGT.