{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:36:17Z","timestamp":1774949777440,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a navigational query language extensively used in ontology and graph database querying. While it is known that containment of CRPQs is EXPSPACE-complete in general, we focus here on severely restricted fragments, which are known to be highly relevant in practice according to several recent studies. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for NP, Pi2p, PSPACE or EXPSPACE.<\/jats:p>","DOI":"10.24963\/kr.2020\/38","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T04:39:16Z","timestamp":1597898356000},"page":"371-380","source":"Crossref","is-referenced-by-count":8,"title":["Containment of Simple Conjunctive Regular Path Queries"],"prefix":"10.24963","author":[{"given":"Diego","family":"Figueira","sequence":"first","affiliation":[{"name":"Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI"}]},{"given":"Adwait","family":"Godbole","sequence":"additional","affiliation":[{"name":"IIT Bombay"}]},{"given":"S.","family":"Krishna","sequence":"additional","affiliation":[{"name":"IIT Bombay"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[{"name":"University of Bayreuth"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"University of Bayreuth"}]},{"given":"Tina","family":"Trautner","sequence":"additional","affiliation":[{"name":"University of Bayreuth"}]}],"member":"10584","event":{"name":"17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}","theme":"Artificial Intelligence","location":"Rhodes, Greece","acronym":"KR-2020","number":"17","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Association for Logic Programming","Center for Perspicuous Computing","European Association for Artificial Intelligence","Ontopic - The Virtual Knowledge Graph Company"],"start":{"date-parts":[[2020,9,12]]},"end":{"date-parts":[[2020,9,18]]}},"container-title":["Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T21:18:37Z","timestamp":1604611117000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2020\/38"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2020\/38","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}