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