[FIG(quote)[
[FIGCAPTION[
[1] [CITE[An Automata-Theoretic Approach to Regular XPath]]
([TIME[2009-06-18 19:30:06 +09:00]])
<https://www.cs.rice.edu/~vardi/papers/dbpl09.pdf>
]FIGCAPTION]

> 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.
> 

]FIG]