摘要

这篇论文的标题是《On the Equivalence between Logic Programming and SETAF》，作者是来自巴西塞阿拉联邦大学的 João Alcântara、Renan Cordeiro 和 Samy Sá。该论文主要探讨了逻辑编程（Logic Programming）和集合攻击框架（SETAF）之间的等价关系。论文的主要内容是提供了从正常逻辑程序（NLP）到 SETAF 的翻译，反之亦然，从 SETAF 到 NLP 的翻译。作者证明了它们的语义之间存在对偶等价性，包括 L-稳定和半稳定语义之间的等价性。此外，对于一类称为无冗余原子逻辑程序（RFALP）的 NLP，还存在结构等价性，因为这些来回翻译是彼此的逆。然后，作者通过一系列文献中已知的程序转换，将任何 NLP 转换为等价的 RFALP，从而证明了 RFALP 与 NLP 具有相同的表达能力。作者还证明了这些程序转换是可合流的，这意味着每个 NLP 将被转换为唯一的 RFALP。

原理

在这篇论文中，作者提出了一种新的方法来证明逻辑编程和集合攻击框架之间的等价关系。具体来说，作者通过引入两个函数：L2IP 将解释与每个标签相关联，而 I2LP 将标签与每个解释相关联。然后，作者研究了它们在什么条件下是彼此的逆，并利用这些结果来证明语义之间的等价性。这些函数本质上允许我们将解释和标签视为可互换的实体，进一步加强了逻辑编程和集合攻击框架之间的联系。

流程

1. 从 NLP 到 SETAF 的翻译：
   • 首先，作者将 NLP 规则直接转换为论点。
   • 然后，作者使用（Caminada 等人，2015b）中提出的方法来构造语句，并将具有相同头的规则对应的语句分组形成一个论点。
   • 最后，作者使用定义的论点和攻击关系来定义与 NLP 相关联的 SETAF。
2. 从 SETAF 到 NLP 的翻译：
   • 对于任何 SETAF A，作者定义了一个相关联的 NLP PA，其中包含了 A 中的所有论点和攻击关系。
   • 然后，作者证明了从 NLP 到 SETAF 的翻译和从 SETAF 到 NLP 的翻译是彼此的逆。
3. 无冗余原子逻辑程序（RFALP）：
   • 作者定义了一类特殊的 NLP，称为无冗余原子逻辑程序（RFALP）。
   • 作者证明了对于 RFALP，从 NLP 到 SETAF 的翻译和从 SETAF 到 NLP 的翻译不仅在语义上是等价的，而且在结构上也是等价的。
   • 作者还证明了任何 NLP 都可以通过一系列程序转换转换为等价的 RFALP，并且这些程序转换是可合流的，这意味着每个 NLP 将被转换为唯一的 RFALP。

应用

这篇论文的结果增强了我们对逻辑编程和集合攻击框架本质上是相同形式主义的理解。此外，作者还证明了无冗余原子逻辑程序与集合攻击框架之间的等价性，这为逻辑编程社区提供了有价值的贡献。通过将逻辑编程与集合攻击框架联系起来，我们可以更好地理解逻辑编程中的语义和结构，并为逻辑编程的应用提供新的思路和方法。