Deciding the Borel complexity of regular tree languages
Alessandro Facchini, Henryk Michalewski · 2016
Abstract. We show that it is decidable whether a given a regular tree language belongs to the class∆02 of the Borel hierarchy, or equivalently whether the Wadge degree of a regular tree language is countable. 1