重构答案集语义基础原则,让逻辑程序更合理可靠。
Refining Gelfond Rationality Principle: Towards More Comprehensive Foundational Principles for Answer Set Semantics
- 以最小性、无循环论证等为核心,重新定义答案集构造原则。
- 提出新语义框架,能排除不合理解并保持知识最小化。
- 适合逻辑编程与知识表示研究者参考,提升形式系统严谨性。
非单调逻辑编程是答案集编程(ASP)的基础。自1988年Gelfond和Lifschitz提出简单正规逻辑程序的答案集语义以来,多种扩展语义被提出。本文探讨两个核心问题:(1) 最小模型性质、约束单调性及奠基性是否应为通用答案集语义的强制条件?(2) 若否,哪些性质可作为一般性原则?首先指出,前述三条件有时过强,强制执行可能排除预期答案集。其次,通过将Gelfond的理性原则细化为:充分支持性、默认否定下的最小性、信念否定下的最小性,来改进答案集构造原则。充分支持性确保每个答案集可通过满足层级映射的若-则规则构造,避免循环推理;两项最小性原则保证形式系统在答案集和世界视图层面均最小化知识。第三,将充分支持性概念分别扩展至答案集和世界视图。第四,基于修正后的GAS原则定义新的答案集语义。第五,以修正原则为基准,直观评估现有语义。最后,分析其计算复杂度。
原文摘要 · Abstract (English)
Non-monotonic logic programming is the basis for a declarative problem solving paradigm known as answer set programming (ASP). Departing from the seminal definition by Gelfond and Lifschitz in 1988 for simple normal logic programs, various answer set semantics have been proposed for extensions. We consider two important questions: (1) Should the minimal model property, constraint monotonicity and foundedness as defined in the literature be mandatory conditions for an answer set semantics in general? (2) If not, what other properties could be considered as general principles for answer set semantics? We address the two questions. First, it seems that the three aforementioned conditions may sometimes be too strong, and we illustrate with examples that enforcing them may exclude expected answer sets. Second, we evolve the Gelfond answer set (GAS) principles for answer set construction by refining the Gelfond's rationality principle to well-supportedness, minimality w.r.t. negation by default and minimality w.r.t. epistemic negation. The principle of well-supportedness guarantees that every answer set is constructible from if-then rules obeying a level mapping and is thus free of circular justification, while the two minimality principles ensure that the formalism minimizes knowledge both at the level of answer sets and of world views. Third, to embody the refined GAS principles, we extend the notion of well-supportedness substantially to answer sets and world views, respectively. Fourth, we define new answer set semantics in terms of the refined GAS principles. Fifth, we use the refined GAS principles as an alternative baseline to intuitively assess the existing answer set semantics. Finally, we analyze the computational complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。