View article

It has been proved by Niwiński and Walukiewicz that a deterministic tree language is either Π-complete or it is on the level Π of the Borel hierarchy, and that it can be decided effectively which of the two takes place. In this paper we show how to decide if the language recognized by a given deterministic tree automaton is on the Π, the Σ, or the Σ level. Together with the previous results it gives a procedure calculating the exact position of a deterministic tree language in the topological hierarchy.