paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Canonical Models and the Complexity of Modal Team Logic

规范模型与模态团队逻辑的复杂度
LMCS vol.Volume 15, Issue 22019匹配度 2/10 · 该论文研究模态团队逻辑 MTL 的可满足性与复杂度分类(TOWER(poly) 完全性),属于纯逻辑与复杂度理论工作,与用户关注的方向(面向 ML/Agentic 程序的静态分析、LLM 辅助形式化验证、浮点程序分析、贝叶斯程序分析)没有直接交叉,也不涉及工具落地或 benchmark 设计。仅因同属形式化方法/逻辑这一大背景而有极微弱关联。引用 7 inbox
Martin Lück
crossref: 2026-09-10

AI 速览

一句话:引入规范模型方法,将MTL可满足性归约为模型检测,并证明其完全性位于TOWER(poly)。

本文研究模态团队逻辑 MTL,即布尔否定下封闭的模态逻辑 ML 的团队语义扩展。其依赖、独立与包含片段已有较好理解,但完整 MTL 的可满足性因无限制布尔否定长期缺乏复杂度分类。作者将规范模型概念引入团队语义,通过构造规范模型把可满足性归约为简单模型检测,并证明 MTL 公式能高效强制规范性,故该归约最优。为刻画复杂度,作者引入非初等类 TOWER(poly),证明 MTL 的可满足性与有效性是其完全问题;有界模态深度片段则对初等层次各级(多项式次交替)完全。困难性结果在严格/宽松模态算子与分裂析取语义下,以及自反传递框架上均成立。

问题
完整模态团队逻辑 MTL 的可满足性因无限制布尔否定而长期难以进行复杂度理论分类;有界模态深度片段的复杂度层次也未明确。
方法
引入团队语义下的规范模型,构造规范模型将 MTL 可满足性归约为模型检测,并证明公式可高效强制规范性以说明归约最优;引入复杂度类 TOWER(poly) 进行刻画。
评估
理论证明:证得 MTL 可满足性与有效性对 TOWER(poly) 完全,有界模态深度片段对初等层次各级(多项式次交替)完全,并在严格/宽松模态算子与分裂析取语义、自反传递框架类上证明困难性。
原文摘要(Abstract)

We study modal team logic MTL, the team-semantical extension of modal logic ML closed under Boolean negation. Its fragments, such as modal dependence, independence, and inclusion logic, are well-understood. However, due to the unrestricted Boolean negation, the satisfiability problem of full MTL has been notoriously resistant to a complexity theoretical classification. In our approach, we introduce the notion of canonical models into the team-semantical setting. By construction of such a model, we reduce the satisfiability problem of MTL to simple model checking. Afterwards, we show that this approach is optimal in the sense that MTL-formulas can efficiently enforce canonicity. Furthermore, to capture these results in terms of complexity, we introduce a non-elementary complexity class, TOWER(poly), and prove that it contains satisfiability and validity of MTL as complete problems. We also prove that the fragments of MTL with bounded modal depth are complete for the levels of the elementary hierarchy (with polynomially many alternations). The respective hardness results hold for both strict or lax semantics of the modal operators and the splitting disjunction, and also over the class of reflexive and transitive frames.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot804,
  title = {Canonical Models and the Complexity of Modal Team Logic},
  author = {Martin Lück},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 2},
  year = {2019},
  doi = {10.23638/lmcs-15(2:2)2019}
}