paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Scalar and Vectorial mu-calculus with Atoms

带原子的标量与向量 μ-演算
LMCS vol.Volume 15, Issue 42019匹配度 1/10 · 该论文是纯逻辑与自动机理论研究,讨论带原子的模态 μ-演算、模型检测与可满足性,不涉及 LLM/Agent、ML 系统静态分析、浮点程序分析或贝叶斯程序分析;虽与形式验证/模型检测相关,但距离用户核心研究方向很远。引用 0 inbox
Bartek Klin, Mateusz Łełyk
crossref: 2026-09-10

AI 速览

一句话:研究带原子的模态 μ-演算扩展:轨道有限结构上模型检测可判定且对应奇偶博弈,但可满足性不可判定。

本文研究将模态 μ-演算扩展到带原子集合的设定,并考察其基本性质。作者定义标量与向量两种带原子 μ-演算语法,分析其模型检测、博弈对应与可满足性。关键结果是:在轨道有限结构上模型检测可判定,且与奇偶博弈的对应关系成立;但可满足性问题不可判定。作者进一步刻画原子增强 μ-演算的表达力限制,说明其表达力取决于所用原子结构以及基本语法与向量语法之间的选择。

问题
如何将模态 μ-演算扩展到带原子的集合,并确定其模型检测、可满足性和表达力等基本性质。
方法
定义标量与向量两种带原子 μ-演算语法,研究其语义,并借助轨道有限结构与奇偶博弈进行分析。
评估
通过理论证明表明:模型检测在轨道有限结构上可判定且对应奇偶博弈,可满足性不可判定;并比较不同原子结构与语法选择的表达力。
原文摘要(Abstract)

We study an extension of modal $\mu$-calculus to sets with atoms and we study its basic properties. Model checking is decidable on orbit-finite structures, and a correspondence to parity games holds. On the other hand, satisfiability becomes undecidable. We also show expressive limitations of atom-enriched $\mu$-calculi, and explain how their expressive power depends on the structure of atoms used, and on the choice between basic or vectorial syntax.

链接与引用

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

BibTeX
@article{paperbot746,
  title = {Scalar and Vectorial mu-calculus with Atoms},
  author = {Bartek Klin and Mateusz Łełyk},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 4},
  year = {2019},
  doi = {10.23638/lmcs-15(4:5)2019}
}