论文标题
使用路径查询精确学习多列和几乎树
Exact Learning of Multitrees and Almost-Trees Using Path Queries
论文作者
论文摘要
给定一个有向图的G =（v，e），路径查询，路径（u，v），返回是否有从u到v中的u到v中的有向路径，对于u，v中的v vertices。仅给定v中，通常不可能使用路径查询中的g学习所有边缘，因为路径查询无法检测到横向的eDGE。在本文中，我们研究了使用路径查询可能学习G时的案例精确学习的查询复杂性。特别是，我们为包括蝴蝶网络在内的多阶段和几乎树木提供有效的学习算法以及下限。
Given a directed graph, G=(V,E), a path query, path(u,v), returns whether there is a directed path from u to v in G, for u,v vertices in V. Given only V, exactly learning all the edges in G using path queries is often impossible, since path queries cannot detect transitive edges. In this paper, we study the query complexity of exact learning for cases when learning G is possible using path queries. In particular, we provide efficient learning algorithms, as well as lower bounds, for multitrees and almost-trees, including butterfly networks.
