Nie jesteś zalogowany | Zaloguj się

On Boolean closed full trios for ω-words

Prelegent(ci)
Mikołaj Bojańczyk
Afiliacja
Uniwersytet Warszawski
Termin
9 października 2019 14:15
Pokój
p. 5050
Seminarium
Seminarium „Teoria automatów”

Zetzsche and Lohrey showed that if a class of languages of finite words:

1. is closed under Boolean combinations; and

2. is closed under images of rational transductions (=NFA’s with output);

3. contains at least one non-regular language  

then the class contains the entire arithmetic hierarchy (in particular, all decidable languages). We show that the same result holds for languages of ω-words.