研究命题依赖逻辑中偏好推理的复杂性与性质，发现其不满足经典系统P。
On the Complexity and Properties of Preferential Propositional Dependence Logic
- 基于团队语义和依赖原子，分析偏好推理的逻辑特性
- 揭示偏好依赖逻辑在特定条件下才满足System P，且不适用于普通团队逻辑
- 给出经典蕴含与依赖蕴含在非平凡偏好模型中的表达方式
本文研究命题依赖逻辑中基于团队语义的KLM风格偏好推理的复杂性与性质。结果显示，偏好团队推理具有累积性，但违反System P。文章给出了偏好命题依赖逻辑满足System P的完整刻画条件。令人意外的是，这些条件无法推广至一般的偏好团队命题逻辑。此外，文章展示了如何用非平凡偏好模型表达经典蕴含与依赖逻辑蕴含。最后，针对两种自然表示形式，给出了偏好团队推理的复杂性结果，包括对经典（非团队）偏好推理的新复杂度结论。
原文摘要 · Abstract (English)
This paper considers the complexity and properties of KLM-style preferential reasoning in the setting of propositional logic with team semantics and dependence atoms, also known as propositional dependence logic. Preferential team-based reasoning is shown to be cumulative, yet violates System~P. We give intuitive conditions that fully characterise those cases where preferential propositional dependence logic satisfies System~P. We show that these characterisations do, surprisingly, not carry over to preferential team-based propositional logic. Furthermore, we show how classical entailment and dependence logic entailment can be expressed in terms of non-trivial preferential models. Finally, we present the complexity of preferential team-based reasoning for two natural representations. This includes novel complexity results for classical (non-team-based) preferential reasoning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。