发帖
雷达卡
摘要翻译：
Gebser和Schaub利用初等环的概念，仅考虑初等环的环公式，对Lin和Zhao关于环公式的定理进行了改进。在本文中，我们重新定义了初等循环的定义，并将其推广到析取程序，研究了初等循环的几个性质，包括极大初等循环与极小无根据集的关系。这些结果提供了关于基本循环的稳定模型语义的有用见解。对于非析取程序，利用初等环的图论刻画，证明了初等环的识别问题是可处理的。另一方面，我们证明了对于一个析取程序，相应的问题是{\sf coNP}-完全的。基于初等循环的概念，我们给出了无首次初等循环(HEF)程序类，它严格推广了Ben-Eliyahu和Dechter的无首次循环(HCF)程序类。与HCF程序一样，HEF程序可以在多项式时间内通过将头部原子移入主体而变成等价的非析取程序。
---
英文标题：
《On Elementary Loops of Logic Programs》
---
作者：
Martin Gebser, Joohyung Lee and Yuliya Lierler
---
最新提交年份：
2011
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
Using the notion of an elementary loop, Gebser and Schaub refined the theorem on loop formulas due to Lin and Zhao by considering loop formulas of elementary loops only. In this article, we reformulate their 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 show that the corresponding problem is {\sf 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 due to Ben-Eliyahu and Dechter. 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.
---
PDF链接：
https://arxiv.org/pdf/1012.5847
京公网安备 11010802022788号
