paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Modal Logics with Composition on Finite Forests

有限森林上带复合算子的模态逻辑
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 4/10 · 论文研究有限森林上模态逻辑与分离逻辑的表达力和可满足性复杂度,属于形式化验证与程序逻辑的理论基础,与分离逻辑等程序验证工具的理论背景有关。但它不涉及静态分析、LLM/Agent 交叉、浮点程序分析或贝叶斯程序分析,也缺乏工程实现与工业落地,因此与用户当前核心研究方向仅有间接关联。引用 5 inbox
Bartosz Bednarczyk, Stéphane Demri, Raul Fervari, Alessio Mansutti
crossref: 2026-09-12

AI 速览

一句话:证明有限森林上两种带复合算子的模态逻辑的表达力与可满足性复杂度,并解决相关公开问题。

论文研究在有限森林上解释、并带有用于推理子模型的标准模态词的两类模态逻辑 ML(|) 与 ML(*)。ML(|) 在模态逻辑 K 上加入 ambient logic 的复合算子 |,ML(*) 则加入分离逻辑的分离合取 *,两者本质上都是二阶算子。作者比较了它们的表达力:ML(|) 与树上的 graded modal logic GML 表达力相同,而 ML(*) 严格弱于 GML。可满足性方面,ML(*) 是 Tower-完全的,ML(|) 仅为 AExpPol-完全的,这一反差在表达力对比下出人意料。作为副产品,还解决了静态 ambient logic 与模态分离逻辑等姊妹逻辑的若干公开问题。

问题
两类在有限森林上带二阶复合算子的模态逻辑 ML(|) 与 ML(*) 的表达力与可满足性复杂度尚未被刻画,且相关姊妹逻辑存在公开问题。
方法
通过表达力比较(与 GML 对比)以及对可满足性问题复杂度上界与下界的分析,建立 ML(|) 与 ML(*) 的精确复杂度刻画。
评估
以理论证明给出表达力包含与严格分离结果,证明 ML(*) 可满足性为 Tower-完全、ML(|) 为 AExpPol-完全,并据此解决静态 ambient logic 与模态分离逻辑等公开问题。
原文摘要(Abstract)

We study the expressivity and complexity of two modal logics interpreted on finite forests and equipped with standard modalities to reason on submodels. The logic ML(|) extends the modal logic K with the composition operator | from ambient logic, whereas ML(*) features the separating conjunction * from separation logic. Both operators are second-order in nature. We show that ML(|) is as expressive as the graded modal logic GML (on trees) whereas ML(*) is strictly less expressive than GML. Moreover, we establish that the satisfiability problem is Tower-complete for ML(*), whereas it is (only) AExpPol-complete for ML(|), a result which is surprising given their relative expressivity. As by-products, we solve open problems related to sister logics such as static ambient logic and modal separation logic.

链接与引用

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

BibTeX
@inproceedings{paperbot5486,
  title = {Modal Logics with Composition on Finite Forests},
  author = {Bartosz Bednarczyk and Stéphane Demri and Raul Fervari and Alessio Mansutti},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394787}
}