Extensions of ω-Regular Languages

2020/02/21 by Mikołaj Bojańczyk, Edon Kelmendi, Bojańczyk, Mikołaj +5
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2002.09393

openalex publication_date 2020/02/21 · openalex created_date 2022/07/26 · openalex updated_date 2026/08/04

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.

Related

• Monadic Monadic Second Order Logic
• Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic
• Languages ordered by the subword order
• The Regular Languages of First-Order Logic with One Alternation
• Lecture Notes on Monadic First- and Second-Order Logic on Strings