Affiliations: Institute of Informatics, University of Warsaw, Poland.
E-mails: bojan@mimuw.edu.pl, niwinski@mimuw.edu.pl | The Blavatnik School of Computer Science, Tel Aviv
University, Israel. E-mail: rabinoa@post.tau.ac.il | Faculty of Mathematics, Informatics, and Mechanics,
University of Warsaw, Poland. E-mails: ar237576@students.mimuw.edu.pl,
mskrzypczak@mimuw.edu.pl
Abstract: An infinite binaryword can be identified with a branch in the full
binary tree. We consider sets of branches definable in monadic second-order
logic over the tree, where we allow some extra monadic predicates on the nodes.
We show that this class equals to the Boolean combinations of sets in the Borel
class Σ^0_2 over the Cantor discontinuum. Note that the last coincides with the
Borel complexity of ω-regular languages.
