episciences.org_1564_1638771613
1638771613
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
1860-5974
06
09
2015
Volume 11, Issue 2
Containment for Conditional Tree Patterns
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.
06
09
2015
1564
arXiv:1503.02210
10.2168/LMCS-11(2:4)2015
https://lmcs.episciences.org/1564