arXiv:2607.21203cs.AI2026-07

提出更严格的描述逻辑程序语义,保持计算高效且与逻辑编程更一致。

A New Well-Supported Semantics for Description Logic Programs

  • 新语义对本体原子判断更严格,避免循环依赖
  • 一致性问题仍为NP完全,未升至多项式层级第二层
  • 适合关注逻辑编程一致性与计算效率的研究者

描述逻辑程序是结合规则与本体的强大形式化工具。现有良好的支持语义确保答案集不依赖循环依赖,但存在两个局限:一致性问题的计算复杂度上升至多项式层级第二层,且缺乏归约变换的刻画。本文提出一种新语义,对本体原子的评估更加严格,保持一致性问题仍为NP完全,而非升至第二层。我们识别出一类语法上可定义的描述逻辑程序,其新语义与旧语义等价。通过不动点算子和基于归约的变换刻画新语义。新语义是原良好支持语义的真子集,既保留原有良好支持性,又引入更严格的定义。因其与逻辑编程的相似性,我们更偏好此新定义。

原文摘要 · Abstract (English)

Description logic programs are a powerful formalism for combining rules with ontologies. The well-supported semantics for description logic programs ensures that no answer sets rely on cyclic dependencies. Most popular semantics for logic programming have this property of well-supportedness. We recognize two limitations of the current well-supported semantics for DL programs: its increased computational complexity for the consistency problem and its lack of a reduct transformation characterization. In this work, we present a new semantics which evaluates ontological atoms more strictly than the current semantics. This keeps the complexity of its consistency problem NP-complete, rather than increasing it to the second level of the polynomial hierarchy. Additionally, we identify a syntactic class of description logic programs for which our new semantics is equivalent to the current semantics. We characterize our semantics using a fixpoint operator and a reduct-based transformation. Our new semantics is a strict subset of the current well-supported semantics, so it maintains the prior notion of well-supportedness while inducing its own stricter notion. We prefer our new notion of well-supportedness due to its similarities with logic programming.

描述逻辑程序语义逻辑编程复杂性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。