Bojańczyk, Mikołaj; Niwiński, Damian; Rabinovich, Alexander; Radziwończyk-Syta, Adam; Skrzypczak, Michał On the Borel complexity of MSO definable sets of branches. (English) Zbl 1206.03041 Fundam. Inform. 98, No. 4, 337-349 (2010). Summary: An infinite binary word 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 \(\pmb\Sigma^0_2\) over the Cantor discontinuum. Note that the last coincides with the Borel complexity of \(\omega\)-regular languages. Cited in 2 Documents MSC: 03D05 Automata and formal grammars in connection with logical questions 03E15 Descriptive set theory Keywords:infinite words; trees; Borel hierarchy; automata; monadic second-order logic PDFBibTeX XMLCite \textit{M. Bojańczyk} et al., Fundam. Inform. 98, No. 4, 337--349 (2010; Zbl 1206.03041) Full Text: DOI