On the Borel Complexity of MSO Definable Sets of Branches

Issue title: Bridging Logic and Computer Science: to Johann A. Makowsky for his 60th birthday

Article type: Research Article

Authors: Bojańczyk, Mikołaj | Niwiński, Damian | Rabinovich, Alexander | Radziwończyk-Syta, Adam | Skrzypczak, Michał

Affiliations: Institute of Informatics, University of Warsaw, Poland. E-mails: [email protected], [email protected] | The Blavatnik School of Computer Science, Tel Aviv University, Israel. E-mail: [email protected] | Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Poland. E-mails: [email protected], [email protected]

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.

Keywords: Monadic 2nd-order logic, infinite words, trees, Borel hierarchy, automata

DOI: 10.3233/FI-2010-231

Journal: Fundamenta Informaticae, vol. 98, no. 4, pp. 337-349, 2010