arXiv Open Access 2020

Extensions of $ω$-Regular Languages

Mikołaj Bojańczyk Edon Kelmendi Rafał Stefański Georg Zetzsche

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.FL cs.LO

Penulis (4)

Mikołaj Bojańczyk

Edon Kelmendi

Rafał Stefański

Georg Zetzsche

Format Sitasi

APA MLA BibTeX

Bojańczyk, M., Kelmendi, E., Stefański, R., Zetzsche, G. (2020). Extensions of $ω$-Regular Languages. https://arxiv.org/abs/2002.09393

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓