1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 unknown
We show that a tree language recognized by a deterministic parity automaton is either hard for the co-Büchi level and therefore cannot be recognized by a weak alternating automaton, or is on a very low evel in the hierarchy of weak alternating automata. A topological counterpart of this property is that a deterministic tree language is either 1 1 complete (and hence non Borel), or it is on the level 0 3 of the Borel hierarchy. We also give a new simple proof of the strictness of the hierarchy of weak alternating automata. For Anatol Slissenko at his 60th birthday.
Theoretical Computer Science, 2003, Vol 1, Issue 303, p. 215-231