{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:38Z","timestamp":1753889738467,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,6,9]],"date-time":"2015-06-09T00:00:00Z","timestamp":1433808000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>A Conditional Tree Pattern (CTP) expands an XML tree pattern with labels\nattached to the descendant edges. These labels can be XML element names or\nBoolean CTPs. The meaning of a descendant edge labelled by A and ending in a\nnode labelled by B is a path of child steps ending in a B node such that all\nintermediate nodes are A nodes. In effect this expresses the until B, A holds\nconstruction from temporal logic.This paper studies the containment problem for\nCTP. For tree patterns (TP), this problem is known to be coNP-complete. We show\nthat it is PSPACE-complete for CTP. This increase in complexity is due to the\nfact that CTP is expressive enough to encode an unrestricted form of label\nnegation: ${*}\\setminus a$, meaning \"any node except an a-node\". Containment of\nTP expanded with this type of negation is already PSPACE-hard. CTP is a\npositive, forward, first order fragment of Regular XPath. Unlike TP, CTP\nexpanded with disjunction is not equivalent to unions of CTP's. Like TP, CTP is\na natural fragment to consider: CTP is closed under intersections and CTP with\ndisjunction is equally expressive as positive existential first order logic\nexpanded with the until operator.<\/jats:p>","DOI":"10.2168\/lmcs-11(2:4)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:13:12Z","timestamp":1479733992000},"source":"Crossref","is-referenced-by-count":2,"title":["Containment for Conditional Tree Patterns"],"prefix":"10.46298","volume":"Volume 11, Issue 2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7507-116X","authenticated-orcid":false,"given":"Alessandro","family":"Facchini","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2076-2750","authenticated-orcid":false,"given":"Yoichi","family":"Hirai","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3255-3729","authenticated-orcid":false,"given":"Maarten","family":"Marx","sequence":"additional","affiliation":[]},{"given":"Evgeny","family":"Sherkhonov","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2015,6,9]]},"reference":[{"key":"1003:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1564\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1564\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:06:33Z","timestamp":1681243593000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1564"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,9]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(2:4)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1503.02210","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1503.02210","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,6,9]]},"article-number":"1564"}}