  We define a new kind of automata recognizing properties of data words or data
trees and prove that the automata capture all queries definable in Regular
XPath. We show that the automata-theoretic approach may be applied to answer
decidability and expressibility questions for XPath.
