Decidable classes of documents for XPath
Vince Bárány, Mikołaj Bojańczyk, Diego Figueira, Paweł Parys · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2012
We study the satisfiability problem for XPath over XML documents of bounded depth. We define two parameters, called match width and braid width, that assign a number to any class of documents. We show that for all k, satisfiability for XPath restricted to bounded depth documents with match width at most k is decidable; and that XPath is undecidable on any class of documents with unbounded braid width. We conjecture that these two parameters are equivalent, in the sense that a class of documents has bounded match width iff it has bounded braid width.