• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>AI communications >Dynamic Magic Sets and super-coherent answer set programs
【24h】

Dynamic Magic Sets and super-coherent answer set programs

机译：动态魔术集和超连贯答案集程序

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

For many practical applications of ASP, for instance data integration or planning, query answering is important, and therefore query optimization techniques for ASP are of great interest. Magic Sets are one of these techniques, originally defined for Datalog queries (ASP without disjunction and negation). Dynamic Magic Sets (DMS) are an extension of this technique, which has been proved to be sound and complete for query answering over ASP programs with stratified negation.A distinguishing feature of DMS is that the optimization can be exploited also during the non-deterministic phase of ASP engines. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space, which may result in exponential performance gains.In this paper, the correctness of DMS is formally established and proved for brave and cautious reasoning over the class of super-coherent ASP programs (ASP~(SC) programs). ASP~(SC) programs guarantee consistency (i.e., have answer sets) when an arbitrary set of facts is added to them. This result generalizes the applicability of DMS, since the class of ASP~(SC) programs is richer than ASP programs with stratified negation, and in particular includes all odd-cycle-free programs. DMS has been implemented as an extension of DLV, and the effectiveness of DMS for ASP~(SC) programs is empirically confirmed by experimental results with this system.
机译：对于ASP的许多实际应用，例如数据集成或计划，查询应答非常重要，因此，ASP的查询优化技术引起了人们的极大兴趣。魔术集是这些技术中的一种，最初是为数据记录查询（ASP而不进行取反和取反）定义的。动态魔术集（DMS）是该技术的扩展，已被证明是可靠的和完整的，可以对带有分层否定的ASP程序进行查询回答。DMS的一个显着特征是，在不确定情况下也可以利用优化ASP引擎的阶段。特别是，在计算过程中做出一些假设之后，在这些假设下，程序的某些部分可能与查询无关。这允许对搜索空间进行动态修剪，这可能会导致指数级的性能提升。本文正式建立了DMS的正确性，并证明了对于超级相干ASP程序（ASP〜（SC ） 程式）。当向ASP〜（SC）程序添加任意事实集时，它们可以保证一致性（即具有答案集）。该结果概括了DMS的适用性，因为ASP〜（SC）程序的类别比带分层否定的ASP程序更丰富，尤其是包括所有无奇数循环的程序。 DMS已被实现为DLV的扩展，该系统的实验结果从经验上证实了DMS对于ASP〜（SC）程序的有效性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号