The evaluation of XPath expressions plays a central role in accessing XML documents and therefore may be used in XML database systems for different components. We demonstrate that different applications ranging from access control to transaction synchronization to the reuse of query results have very similar requirements to the evaluation of XPath expressions, which can be solved by the same two steps. Firstly, we compute from each XPath expression a regular expression of the selected node paths and right-shuffle predicate filters to the selected nodes. Secondly, we describe the treatment of predicate filters which may be used in XPath expressions for queries, access control, and synchronization, and present a fast predicate evaluator for these predicates. Finally, we introduce the concept of “fall-back decisions”, which allow us to use an incomplete but efficient theorem prover, which solves most cases in practice and guarantees correct fallback behavior for the other cases.