Extensions of ω-Regular Languages
Mikolaj Bojanczyk, Edon Kelmendi, Rafal Stefanski, Georg Zetzsche
2020Year
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.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext e9b0fc45-cdda-42d0-9bc3-00b93e20cd07Related papers
- Positive First-order Logic on WordsDenis KuperbergLICS 2021 · 3 citations
- The Regular Languages of First-Order Logic with One AlternationCorentin Barloy, Michaël Cadilhac, Charles Paperman, Thomas ZeumeLICS 2022 · 1 citation
- 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 citations
