...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theory and Practice of Logic Programming >On elementary loops of logic programs
【24h】

On elementary loops of logic programs

机译：在逻辑程序的基本循环上

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

摘要

Using the notion of an elementary loop, Gebser and Schaub (2005. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'05), 53-65) refined the theorem on loop formulas attributable to Lin and Zhao (2004) by considering loop formulas of elementary loops only. In this paper, we reformulate the definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we also show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs attributable to Ben-Eliyahu and Dechter (1994. Annals of Mathematics and Artificial Intelligence 12, 53-87). Like an HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.
机译：Gebser和Schaub（2005.第八届逻辑编程和非单调推理国际会议论文集（LPNMR'05），第53-65页）使用基本循环的概念完善了归因于Lin和Zhao（2004）的循环公式定理仅考虑基本循环的循环公式。在本文中，我们重新定义了基本循环的定义，将其扩展到析取程序，并研究了基本循环的几个属性，包括最大基本循环如何与最小的无基础集相关。结果提供了关于基本循环方面的稳定模型语义的有用见解。对于非析取程序，使用基本循环的图论特征，我们证明了识别基本循环的问题很容易解决。另一方面，我们还表明，对于析取程序，相应的问题是coNP完全的。基于基本循环的概念，我们介绍了“无头循环”（HEF）程序的类，该程序严格概括了归因于Ben-Eliyahu和Dechter（1994）的“无头循环”（HCF）程序的类。数学和人工智能年鉴12，53-87）。像HCF程序一样，通过将头部原子移入人体，可以在多项式时间内将HEF程序转换为等效的非析取程序。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号