{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T21:13:27Z","timestamp":1791148407535,"version":"4.1.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2006,7,26]],"date-time":"2006-07-26T00:00:00Z","timestamp":1153872000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>XPath is a simple language for navigating an XML-tree and returning a set of\nanswer nodes. The focus in this paper is on the complexity of the containment\nproblem for various fragments of XPath. We restrict attention to the most\ncommon XPath expressions which navigate along the child and\/or descendant axis.\nIn addition to basic expressions using only node tests and simple predicates,\nwe also consider disjunction and variables (ranging over nodes). Further, we\ninvestigate the containment problem relative to a given DTD. With respect to\nvariables we study two semantics, (1) the original semantics of XPath, where\nthe values of variables are given by an outer context, and (2) an existential\nsemantics introduced by Deutsch and Tannen, in which the values of variables\nare existentially quantified. In this framework, we establish an exact\nclassification of the complexity of the containment problem for many XPath\nfragments.<\/jats:p>","DOI":"10.2168\/lmcs-2(3:1)2006","type":"journal-article","created":{"date-parts":[[2006,11,23]],"date-time":"2006-11-23T04:27:56Z","timestamp":1164256076000},"source":"Crossref","is-referenced-by-count":49,"title":["On the complexity of XPath containment in the presence of disjunction, DTDs, and variables"],"prefix":"10.46298","volume":"Volume 2, Issue 3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7143-1903","authenticated-orcid":false,"given":"Frank","family":"Neven","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2006,7,26]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2243\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2243\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T16:10:30Z","timestamp":1681229430000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7,26]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-2(3:1)2006","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0606065","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0606065","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7,26]]},"article-number":"2243"}}