2026-07-24T19:04:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3851 2024-03-06T10:34:31Z ddc:004 open_access

Decidable classes of documents for XPath Bárány, Vince Bojanczyk, Mikolaj Figueira, Diego Parys, Pawel XPath XML class automata data trees data words satisfiability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vince Bárány and Mikolaj Bojanczyk and Diego Figueira and Pawel Parys 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.99 urn:nbn:de:0030-drops-38512 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.99 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode