paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Recursion Schemes, the MSO Logic, and the U quantifier

递归方案、MSO 逻辑与 U 量词
LMCS vol.Volume 16, Issue 12020匹配度 2/10 · 该论文属于递归方案模型检测与 MSO 逻辑扩展的纯理论研究,虽与形式化验证/程序分析基础相关,但没有涉及 LLM/Agent、浮点程序分析或贝叶斯程序分析等用户当前核心交叉方向。引用 4 inbox
Paweł Parys
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:证明了带受限 U 量词的 MSO 逻辑对递归方案生成树的模型检测可判定,并给出反射与有效选择性质。

论文研究递归方案(recursion schemes)的模型检测问题:给定高阶递归方案生成的树,判定其是否满足某个逻辑句子。已知 MSO 逻辑下该问题可判定;本文将其扩展到带 U(unbounding)量词的 MSO。U 量词表示某子公式对任意大的有限集合成立,但仅允许用于所有自由变量都表示有限集合的子公式,无限制使用会导致不可判定。作者证明这种受限扩展仍可判定,并进一步说明该逻辑对递归方案生成的树具有反射(reflection)和有效选择(effective selection)性质。

问题
给定高阶递归方案生成的树,判定其是否满足给定逻辑句子;重点是将已知可判定的 MSO 模型检测扩展到带 U 量词的逻辑。
方法
在 MSO 中加入 U(unbounding)量词,但限制其只能用于所有自由变量均表示有限集合的子公式,并对该受限逻辑进行可判定性分析。
评估
通过理论证明建立可判定性,并证明该逻辑对递归方案生成的树具有反射和有效选择性质;同时说明无限制使用 U 量词会导致不可判定。
原文摘要(Abstract)

We study the model-checking problem for recursion schemes: does the tree generated by a given higher-order recursion scheme satisfy a given logical sentence. The problem is known to be decidable for sentences of the MSO logic. We prove decidability for an extension of MSO in which we additionally have an unbounding quantifier U, saying that a subformula is true for arbitrarily large finite sets. This quantifier can be used only for subformulae in which all free variables represent finite sets (while an unrestricted use of the quantifier leads to undecidability). We also show that the logic has the properties of reflection and effective selection for trees generated by recursion schemes.

链接与引用

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

BibTeX
@article{abs-1810-04763,
  title = {Recursion Schemes, the MSO Logic, and the U quantifier},
  author = {Paweł Parys},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 1},
  year = {2020},
  doi = {10.23638/lmcs-16(1:20)2020}
}