Extensions of ω-Regular Languages
Mikolaj Bojanczyk, Edon Kelmendi, Rafal Stefanski, Georg Zetzsche
2020年份
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了最后一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
相关 Paper
- Positive First-order Logic on WordsDenis KuperbergLICS 2021 · 被引用 3 次
- The Regular Languages of First-Order Logic with One AlternationCorentin Barloy, Michaël Cadilhac, Charles Paperman, Thomas ZeumeLICS 2022 · 被引用 1 次
- Characterization and Decidability of FC-Definable Regular LanguagesSam M. Thompson, Nicole Schweikardt, Dominik D. FreydenbergerLICS 2025
- The Uniformisation of Monadic Second-Order Logic over Countable OrdinalsThomas Colcombet, Alexander RabinovichLICS 2026
- First-Order AutomataLuca Geatti, Alessandro Gianola, Nicola GiganteAAAI 2025 · 被引用 3 次
