The expressivity of XPath with transitive closure

Abstract

We extend Core XPath, the navigational fragment of XPath 1.0, with transitive closure and path equalities. The resulting language, Regular XPATH≈, is expressively complete for FO* (first-order logic extended with a transitive closure operator that can be applied to formulas with exactly two free variables). As a corollary, we obtain that Regular XPATH≈ is closed under path intersection and complementation. We also provide characterizations for the *-positive fragment of Regular XPATH≈, and for μRegular XPATH (the extension of Regular XPATH≈ with least fixed points).