  A data tree is an unranked ordered tree whose every node is labelled by a
letter from a finite alphabet and an element ("datum") from an infinite set,
where the latter can only be compared for equality. The article considers
alternating automata on data trees that can move downward and rightward, and
have one register for storing data. The main results are that nonemptiness over
finite data trees is decidable but not primitive recursive, and that
nonemptiness of safety automata is decidable but not elementary. The proofs use
nondeterministic tree automata with faulty counters. Allowing upward moves,
leftward moves, or two registers, each causes undecidability. As corollaries,
decidability is obtained for two data-sensitive fragments of the XPath query
language.
