Extensions of -Regular Languages

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 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.

Authors

• Georg Zetzsche

Keywords

No keywords are indexed for this paper.