Facchini, Alessandro and Hirai, Yoichi and Marx, Maarten and Sherkhonov, Evgeny (2015) Containment for Conditional Tree Patterns. Logical Methods in Computer Science, 11 (2).
Full text not available from this repository.Abstract
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.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Subjects: | Computer sciences > Computer science Computer sciences > Computer science > Computational science foundations Computer sciences > Information systems > Databases |
| Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI |
| Depositing User: | Alessandro Facchini |
| Date Deposited: | 12 Jun 2015 05:18 |
| Last Modified: | 12 Jun 2015 05:18 |
| URI: | http://repository.supsi.ch/id/eprint/6538 |
Actions (login required)
 |
View Item |