Alessandro Facchini ; Yoichi Hirai ; Maarten Marx ; Evgeny Sherkhonov - Containment for Conditional Tree Patterns

lmcs:1564 - Logical Methods in Computer Science, June 9, 2015, Volume 11, Issue 2 - https://doi.org/10.2168/LMCS-11(2:4)2015
Containment for Conditional Tree Patterns

Authors: Alessandro Facchini ; Yoichi Hirai ; Maarten Marx ; Evgeny Sherkhonov

A Conditional Tree Pattern (CTP) expands an XML tree pattern with labels attached to the descendant edges. These labels can be XML element names or Boolean CTPs. The meaning of a descendant edge labelled by A and ending in a node labelled by B is a path of child steps ending in a B node such that all intermediate nodes are A nodes. In effect this expresses the until B, A holds construction from temporal logic.This paper studies the containment problem for CTP. For tree patterns (TP), this problem is known to be coNP-complete. We show that it is PSPACE-complete for CTP. This increase in complexity is due to the fact that CTP is expressive enough to encode an unrestricted form of label negation: ${*}\setminus a$, meaning "any node except an a-node". Containment of TP expanded with this type of negation is already PSPACE-hard. CTP is a positive, forward, first order fragment of Regular XPath. Unlike TP, CTP expanded with disjunction is not equivalent to unions of CTP's. Like TP, CTP is a natural fragment to consider: CTP is closed under intersections and CTP with disjunction is equally expressive as positive existential first order logic expanded with the until operator.

Volume: Volume 11, Issue 2
Published on: June 9, 2015
Submitted on: April 4, 2014
Keywords: Computer Science - Logic in Computer Science