In this paper we present Regular XPath (RXPath), which is a natural extension of

XPath with regular expressions over paths that has the same computational properties as

XPath: linear-time query evaluation and exponential-time reasoning. To establish these

results, we devise a unifying automata-theoretic framework based on two-way weak alternating

tree automata. Specifically, we consider automata that have infinite runs on fi-

nite trees. This enables us to leverage and simplify existing automata-theoretic machinery

and develop algorithms both for query evaluation and for reasoning over queries.

With respect to the latter problem, we consider RXPath as a constraint language, and

study constraint satisfiability, and query satisfiability and containment under constraints

in the setting of RXPath.