完善 Gelfond 的理性原则：迈向答案集语义更全面的基础性原则

《ACM Transactions on Computational Logic》：Refining Gelfond’s Rationality Principle: Towards More Comprehensive Foundational Principles for Answer Set Semantics

　　

摘要AI 摘要

要查看此 AI 生成的摘要，您必须拥有高级访问权限。

了解更多信息登录

摘要

摘要

非单调逻辑编程是声明式问题求解范式——答案集编程（ASP）的基础，其中问题的解由逻辑程序的预期模型（即答案集）编码。在 Gelfond 和 Lifschitz [45] 为简单正常逻辑程序提出的开创性定义之外，人们为扩展形式（如析取逻辑程序和认识逻辑程序）提出了各种答案集语义。在后者中，语义由称为世界视图的答案集集合构成。总体而言，似乎无法在形式上证明某个提案所定义的答案集/世界视图是否与任何由逻辑程序直观表示的问题的解完全对应。因此，有必要发展一些一般性原则，并将其作为基线，以便直观地比较和评估不同的答案集语义和世界视图语义。朝此基线迈进，我们考虑两个重要问题：(1) 文献中定义的最小模型性质、约束单调性和有据性是否应成为一般答案集语义的强制条件？(2) 如果不是，还有哪些其他性质可被视为答案集语义的替代原则？我们通过若干贡献来回答这两个问题。首先，我们通过示例说明，将最小模型、约束单调性和有据性作为强制条件可能会排除某些简单析取程序的预期答案集以及某些认识规范的世界视图。其次，我们通过将 Gelfond 的理性原则细化为有据支持性、关于默认否定的最小性以及关于认识否定的最小性，对用于答案集构建的Gelfond 答案集（GAS）原则 [42] 进行了演进。有据支持性原则保证每个答案集都可通过遵守层次映射的 if-then 规则构建而来，从而避免循环论证，而两种最小性原则确保该形式在答案集层面和世界视图层面都实现知识最小化。因此，我们提议将这三个细化后的 GAS 原则作为一般答案集语义以及特定答案集和世界视图构建的替代原则。第三，为了体现这些细化后的 GAS 原则，我们将有据支持性的概念大幅扩展到答案集和世界视图。第四，我们提议以细化后的 GAS 原则定义答案集语义，分别称为合理答案集语义和合理世界视图语义。第五，我们将细化后的 GAS 原则作为替代基线，直观评估现有的答案集语义是否满足（符合）甚至完全体现这些细化后的 GAS 原则。最后，我们分析了有据支持性以及合理答案集和世界视图语义的计算复杂度，揭示它们作为问题求解的强大宿主。

AI 摘要

AI 生成摘要（实验性）

此摘要由自动化工具生成，未经本文作者撰写或审核。其目的是支持检索、帮助读者评估相关性，并协助相邻研究领域的读者理解该工作。它旨在补充作者提供的摘要，后者仍是论文的主要摘要。全文文章仍是权威版本。点击此处了解更多信息。

点击此处对此摘要的准确性、清晰度和实用性发表评论。这样做将有助于改进和未来的重新生成版本。

要查看此 AI 生成的简明摘要，您必须拥有高级访问权限。