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

Tytuł w języku angielskim

joint work with Edon Kelmendi, Rafał Stefański and Georg Zetzsche

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. 

 

---