paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Decidability of Quasi-Dense Modal Logics

准稠密模态逻辑的可判定性
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 该论文研究模态逻辑的可判定性、证明系统与模板枚举,属于纯逻辑/自动机理论,与用户关注的静态分析、LLM/Agent 辅助程序分析、浮点程序分析及贝叶斯程序分析均无直接关联;仅在“形式化验证的逻辑基础”意义上存在非常间接的联系。引用 9 inbox
Tim Lyon, Piotr Ostropolski-Nalewaja
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:证明准稠密模态逻辑可判定,并给出基于模板枚举的 ExpSpace 判定过程。

对模态逻辑 K 的公理扩张,若加入形如 ⋄^k p → ⋄^n p 的模态归约原则,其可判定性长期悬而未决。本文针对其中满足 0 < k < n 的准稠密逻辑取得进展,证明该大类可判定。作者为这类逻辑定义由析取存在规则组成的新型证明系统;这些规则通常用于数据库理论中的本体规格。作者表明该系统既能生成模态公式的证明,也能生成其模型,并借助精细的模型论论证,将生成的模型编码为有限对象——模板。通过枚举有界大小的模板,论文得到一个 ExpSpace 判定程序,从而证明准稠密模态逻辑的可判定性。

问题
问题:带模态归约原则(形如 ⋄^k p → ⋄^n p)的模态逻辑 K 的公理扩张是否可判定,是长期开放问题;本文聚焦其中 0 < k < n 的准稠密子类。
方法
方法:为准稠密逻辑定义由析取存在规则构成的新证明系统,这类规则常用于数据库理论中的本体规格;该系统可生成模态公式的证明与模型,并通过模型论论证将模型编码为有限模板。
评估
评估:属于理论复杂性研究;通过枚举有界大小的模板,作者得到 ExpSpace 判定程序,从而证明准稠密模态逻辑可判定(无实验评估)。
原文摘要(Abstract)

The decidability of axiomatic extensions of the modal logic K with modal reduction principles, i.e. axioms of the form ⋄kp → ⋄np, has remained a long-standing open problem. In this paper, we make significant progress toward solving this problem and show that decidability holds for a large subclass of these logics, namely, for quasi-dense logics. Such logics are extensions of K with modal reduction axioms such that 0 < k < n (dubbed quasi-density axioms). To prove decidability, we define novel proof systems for quasi-dense logics consisting of disjunctive existential rules, which are first-order formulae typically used to specify ontologies in the context of database theory. We show that such proof systems can be used to generate proofs and models of modal formulae, and provide an intricate model-theoretic argument showing that such generated models can be encoded as finite objects called templates. By enumerating templates of bound size, we obtain an ExpSpace decision procedure as a consequence.

链接与引用

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

BibTeX
@inproceedings{abs-2405-10094,
  title = {Decidability of Quasi-Dense Modal Logics},
  author = {Tim Lyon and Piotr Ostropolski-Nalewaja},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662111}
}