Characterizations for Relativized Notions of Equivalence in Answer Set Programming
Characterizations for Relativized Notions of Equivalence in Answer Set Programming
复制标题
答案集编程中相对化等价概念的表征
DOI：
10.1007/978-3-540-30227-8_16
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
S. Woltran
中科院分区：
文献类型：
--
作者：
S. Woltran
最近在非单调逻辑编程中的研究集中在等价的替代概念上。特别是，强等价和一致等价都被认为是优化逻辑程序(部分)的有用工具。更具体地说，给定一组程序规则和一个可能的优化Q，Strong(Resp.一致)等价性要求添加任何集合的规则(对应于事实)到P和Q同时得到等价方案，即P∪和Q∪具有相同的稳定模型。然而，在实践中，经常需要以这样的方式放宽这一条件，即不再允许在可能的扩展S中出现PorQ中的专用内部原子。在这篇文章中，我们考虑了一致等价和强等价的相对化概念，并通过推广UE-模型性和SE-模式性的概念给出了语义刻画。这些新的刻画以统一的方式捕捉到了等价性的所有概念，包括普通等价性。最后，我们分析了所引入的针对正规逻辑和析取逻辑程序的等价性测试的复杂性。作为副产品，我们将两个程序之间的相对等价测试简化为普通等价测试。这些削减可以作为实施的基础。
Recent research in nonmonotonic logic programming focuses on alternative notions of equivalence. In particular, strong and uniform equivalence are both proposed as useful tools to optimize (parts of) a logic program. More specifically, given a setPof program rules and a possible optimizationQ, strong (resp. uniform) equivalence requires that adding any setSof rules (resp. facts) toPandQsimultaneously results in equivalent programs, i.e.,P∪SandQ∪Spossess the same stable models. However, in practice it is often necessary to relax this condition in such a way, that dedicated internal atoms inPorQare no longer allowed to occur in the possible extensionsS. In this paper, we consider these relativized notions of both uniform and strong equivalence and provide semantical characterizations by generalizing the notions of UE- and SE-modelhood. These new characterizations capture all notions of equivalence including ordinary equivalence in a uniform way. Finally, we analyze the complexity of the introduced equivalence tests for the important classes of normal and disjunctive logic programs. As a by-product, we reduce the tests for relativized equivalences to ordinary equivalence between two programs. These reductions may serve as a basis for implementation.
更新下逻辑程序的等价性
DOI：
--
发表时间：
2004
期刊：
Lecture Notes in Artificial Intelligence Vol.3229
影响因子：
--
作者：
Haruto TAKEDA;Takuya Nishimoto;Shigeki Sagayama;Katsumi Inoue
通讯作者：
Katsumi Inoue