[For the entire collection see Zbl 0587.00019.]
This article continues the point of view that the ”natural” theory of automata on trees is that of automata which are alternating in the sense of D. E. Muller and P. E. Schupp [”Alternating automata on infinite objects and Rabin’s theorem”, Theor. Comput. Sci. (to appear)]. We use alternating automata to give a ”direct” automata-theoretic characterization of the languages of k-ary trees which are weakly- definable, that is to say, definable by a formula in the weak monadic logic of the tree where one allows quantification only over finite sets. We define a ”weak” acceptance condition and show that a language is weakly definable if and only if it is accepted by an alternating automaton using the weak acceptance condition. Secondly, alternating automata are closely related to complexity and we give a simple proof of a bound on the complexity of deciding formulas whose prenex normal form has n alternations of quantifiers.