An extension of data automata that captures XPath
  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. 
Miko{\l}aj Boja\'nczyk (University of Warsaw), S{\l}awomir Lasota   (University of Warsaw)
cs.LO cs.FL