arXiv:2605.21113cs.LOcs.AI2026-05
研究累积命题依赖逻辑的蕴含复杂度，揭示其计算难度边界。
On the Complexity of Entailment for Cumulative Propositional Dependence Logics
- 基于团队语义构建累积逻辑的蕴含判定框架
- 证明了蕴含问题在多项式层次中的精确复杂度
- 适合逻辑与计算复杂性方向的研究者阅读
本文建立了并证明了累积命题依赖逻辑及具有团队语义的累积命题逻辑中蕴含关系的复杂度结果。如近期研究所示，累积逻辑由系统C特征刻画，并被Kraus、Lehmann和Magidor的累积模型精确捕捉。这引出了通过关系模型进行蕴含判定的问题，本文对此进行了专门研究。
原文摘要 · Abstract (English)
This paper establishes and proves complexity results for entailment for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. As recently shown, cumulative logics are famously characterised by System~C and exactly captured by the cumulative models of Kraus, Lehmann and Magidor. This gives rise to the entailment problem via relational models, which is specifically considered here.
逻辑推理复杂度分析团队语义
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。