An extension of data automata that captures XPath

摘要

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