发帖
雷达卡
摘要翻译：
目前，在答案集语义下的逻辑程序设计涉及到许多不同的程序等价概念。这是由于替换等价（称为强等价）和普通等价是不同的概念。前者认为，给定程序P和Q，在任何上下文R中iff P都可以被Q忠实地替换，而后者认为iff P和Q提供相同的输出，即它们具有相同的答案集。强等价和普通等价之间的概念被引入作为比较不完全程序的理论工具，它们要么通过限制所考虑的上下文程序R的句法结构，要么通过限定R中允许出现的原子集A（相对等价）来定义，对于后者，不同的A通常产生适当不同的等价概念。然而，对于前一种方法，结果证明，对R的任何“合理的”句法限制都与普通等价、强等价或一致等价相一致。本文提出了一种等价概念的参数化方法，它一方面对允许出现在上下文规则头中的原子进行定界，另一方面对允许出现在上下文规则体中的原子进行定界，从而同时兼顾了这两种限制。我们引入了一般的语义刻画，其中包括已知的SE模型（用于强等价）和UE模型（用于一致等价）作为特例。此外，我们给出了问题的复杂度范围，并给出了一种可能的实现方法。出现在逻辑程序设计(TPLP)的理论与实践中。
---
英文标题：
《A Common View on Strong, Uniform, and Other Notions of Equivalence in
Answer-Set Programming》
---
作者：
Stefan Woltran
---
最新提交年份：
2007
---
分类信息：
一级分类：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中的材料。
--
一级分类：Computer Science 计算机科学
二级分类：Logic in Computer Science 计算机科学中的逻辑
分类描述：Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.
涵盖计算机科学中逻辑的所有方面，包括有限模型理论，程序逻辑，模态逻辑和程序验证。程序设计语言语义学应该把程序设计语言作为主要的学科领域。大致包括ACM学科类D.2.4、F.3.1、F.4.0、F.4.1和F.4.2中的材料；F.4.3（形式语言）中的一些材料在这里也可能是合适的，尽管计算复杂性通常是更合适的主题领域。
--
---
英文摘要：
Logic programming under the answer-set semantics nowadays deals with numerous different notions of program equivalence. This is due to the fact that equivalence for substitution (known as strong equivalence) and ordinary equivalence are different concepts. The former holds, given programs P and Q, iff P can be faithfully replaced by Q within any context R, while the latter holds iff P and Q provide the same output, that is, they have the same answer sets. Notions in between strong and ordinary equivalence have been introduced as theoretical tools to compare incomplete programs and are defined by either restricting the syntactic structure of the considered context programs R or by bounding the set A of atoms allowed to occur in R (relativized equivalence).For the latter approach, different A yield properly different equivalence notions, in general. For the former approach, however, it turned out that any ``reasonable'' syntactic restriction to R coincides with either ordinary, strong, or uniform equivalence. In this paper, we propose a parameterization for equivalence notions which takes care of both such kinds of restrictions simultaneously by bounding, on the one hand, the atoms which are allowed to occur in the rule heads of the context and, on the other hand, the atoms which are allowed to occur in the rule bodies of the context. We introduce a general semantical characterization which includes known ones as SE-models (for strong equivalence) or UE-models (for uniform equivalence) as special cases. Moreover,we provide complexity bounds for the problem in question and sketch a possible implementation method. To appear in Theory and Practice of Logic Programming (TPLP).
---
PDF链接：
https://arxiv.org/pdf/0712.0948
京公网安备 11010802022788号
