Deciding the Borel complexity of regular tree languages

Abstract

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 regular tree language is countable.

15 pages, 2 figures