paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Extensions of ω-Regular Languages

ω-正则语言的扩展
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 1/10 · 该论文属于纯逻辑与自动机理论，研究 ω-正则语言扩展下 MSO 的可判定性，与研究画像关注的程序分析、Agentic 程序、浮点/贝叶斯程序分析及 LLM 交叉均无直接关联。虽然用户偏好理论形式化工作，但本文缺乏与 PL/AI 或工具落地的连接。引用 0 inbox
Mikołaj Bojańczyk, Edon Kelmendi, Rafał Stefański, Georg Zetzsche
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：证明在 ω-字上添加含中性字母的非 ω-正则语言会使 MSO 扩展不可判定。

论文研究 ω-字上一元二阶逻辑（MSO）的扩展问题：若向该逻辑加入一个非 ω-正则语言 L，所得逻辑是否仍可判定。作者证明，只要 L 含有中性字母（neutral letter），则该扩展逻辑必然是不可判定的。这一结论不依赖于 L 的具体结构，而只取决于中性字母这一语言性质，由此给出了强不可判定性界限。作为推论，ω-字上的 ω-正则语言是唯一同时可判定且对布尔运算封闭的 full trio。该工作为 ω-正则性的逻辑刻画与扩张极限提供了清晰边界。

问题
研究在 ω-字 MSO 逻辑中加入单个非 ω-正则语言后，所得逻辑的可判定性是否保持。
方法
通过分析带中性字母的语言扩张，证明此类扩张必然导致不可判定，并进一步推出可判定且布尔封闭的 full trio 的唯一性。
评估
以数学证明和可判定性、封闭性推论作为评估，未涉及实现或实验。
原文摘要（Abstract）

We consider extensions of monadic second-order logic over ω-words, which are obtained by adding one language that is not ω-regular. We show that if the added language L has a neutral letter, then the resulting logic is necessarily undecidable. A corollary is that the ω-regular languages are the only decidable Boolean-closed full trio over ω-words.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot5503,
  title = {Extensions of ω-Regular Languages},
  author = {Mikołaj Bojańczyk and Edon Kelmendi and Rafał Stefański and Georg Zetzsche},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394779}
}