Containment for Conditional Tree Patterns
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 al...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2015-06-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1564/pdf |
| _version_ | 1797268628302725120 |
|---|---|
| author | Alessandro Facchini Yoichi Hirai Maarten Marx Evgeny Sherkhonov |
| author_facet | Alessandro Facchini Yoichi Hirai Maarten Marx Evgeny Sherkhonov |
| author_sort | Alessandro Facchini |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:35:30Z |
| format | Article |
| id | doaj.art-6336525a3fd14303b6ce448e294faa15 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:30Z |
| publishDate | 2015-06-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-6336525a3fd14303b6ce448e294faa152024-03-08T09:39:43ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742015-06-01Volume 11, Issue 210.2168/LMCS-11(2:4)20151564Containment for Conditional Tree PatternsAlessandro Facchinihttps://orcid.org/0000-0001-7507-116XYoichi Hiraihttps://orcid.org/0000-0003-2076-2750Maarten Marxhttps://orcid.org/0000-0003-3255-3729Evgeny SherkhonovA 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.https://lmcs.episciences.org/1564/pdfcomputer science - logic in computer science |
| spellingShingle | Alessandro Facchini Yoichi Hirai Maarten Marx Evgeny Sherkhonov Containment for Conditional Tree Patterns Logical Methods in Computer Science computer science - logic in computer science |
| title | Containment for Conditional Tree Patterns |
| title_full | Containment for Conditional Tree Patterns |
| title_fullStr | Containment for Conditional Tree Patterns |
| title_full_unstemmed | Containment for Conditional Tree Patterns |
| title_short | Containment for Conditional Tree Patterns |
| title_sort | containment for conditional tree patterns |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/1564/pdf |
| work_keys_str_mv | AT alessandrofacchini containmentforconditionaltreepatterns AT yoichihirai containmentforconditionaltreepatterns AT maartenmarx containmentforconditionaltreepatterns AT evgenysherkhonov containmentforconditionaltreepatterns |