Deciding the Borel complexity of regular tree languages

Alessandro Facchini, Henryk Michalewski

We show that it is decidable whether a given a regular tree language belongs to the class ${\mathbf{\Delta }}_2^0$ of the Borel hierarchy, or equivalently whether the Wadge degree of a regula…