Exact learning of unordered tree patterns from queries
Exact learning of unordered tree patterns from queries
复制标题
从查询中精确学习无序树模式
DOI：
10.1145/307400.307486
复制
发表时间：
1999
影响因子：
3.8
通讯作者：
Prasad Tadepalli
中科院分区：
文献类型：
--
作者：
Thomas R. Amoth;P. Cull;Prasad Tadepalli
我们考虑从扩展了前面的工作的查询中学习树模式[Amoth，cull&Taadealli，1998]。本文中的实例是节点用常量标识符标记的无序树。这些概念是树模式和树模式(无序森林)的并集，树叶用常量或变量标记。树模式匹配其变量被常量子树替换的任何树。对于无序树，对于其中成功匹配要求模式和实例中的子代的数量相同的无序树，显示了使用等价和成员资格/子集查询学习的否定结果。无序树和森林可以通过另一种匹配语义学习，该语义允许实例在每个节点上有额外的子节点。
We consider learning tree patterns from queries extending our preceding work [Amoth, Cull, & Tadepalli, 1998]. The instances in this paper are unordered trees with nodes labeled by constant identifiers. The concepts are tree patterns and unions of tree patterns (unordered forests) with leaves labeled with constants or variables. A tree pattern matches any tree with its variables replaced with constant subtrees. A negative result for learning with equivalence and membership/subset queries is shown for unordered trees where a successful match requires the number of children in the pattern and instance to be the same. Unordered trees and forests are shown to be learnable with an alternative matching semantics that allows an instance to have extra children at each node.