Decidable classes of documents for XPath. (English) Zbl 1354.68071

Bárány, Vince; Bojanczyk, Mikołaj; Figueira, Diego; Parys, Paweł

D’Souza, Deepak (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2012). Selected papers based on the presentations at the 32nd conference, Hyderabad, India, December 15–17, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-47-7). LIPIcs – Leibniz International Proceedings in Informatics 18, 99-111 (2012).

Summary: 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.
For the entire collection see [Zbl 1256.68007].

MSC:

68P15	Database theory
03B25	Decidability of theories and sets of sentences
03B70	Logic in computer science
68Q45	Formal languages and automata

Keywords:

XPath; XML; class automata; data trees; data words; satisfiability