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

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Oct. 9, 2019, 2:15 p.m.

Room

room 5050

Title in Polish

On Boolean closed full trios for ω-words

Seminar

Seminar Automata Theory

---

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. 

 

---