Extensions of ω-regular Languages
Edon Kelmendi ( University of Oxford )
- 11:00 12th March 2020 ( week 8, Hilary Term 2020 )051
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 cone over ω-words.
Joint work with: Mikołaj Bojańczyk, Rafał Stefański and Georg Zetzsche.