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

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.