{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:33:27Z","timestamp":1755999207384,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,5]]},"abstract":"<jats:p>We show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs). A previous result by Barcel\\'o, Romero, and Vardi [SIAM Journal on Computing, 2016] has shown decidability for the case $k=1$, and here we extend this result showing that decidability in fact holds for any arbitrary $k\\geq 1$. The algorithm is in 2ExpSpace, but for the restricted but practically relevant case where all regular expressions of the query are of the form $a^*$ or $(a_1 + \\dotsb + a_n)$ we show that the complexity of the problem drops to $\\Pi^P_2$.   We also investigate the related problem of approximating a UC2RPQ by queries of small tree-width. We exhibit an algorithm which, for any fixed number $k$, builds the maximal under-approximation of tree-width $k$ of a UC2RPQ. The maximal under-approximation of tree-width $k$ of a query $q$ is a query $q'$ of tree-width $k$ which is contained in $q$ in a maximal and unique way, that is, such that for every query $q''$ of tree-width $k$, if $q''$ is contained in $q$ then $q''$ is also contained in $q'$.   Our approach is shown to be robust, in the sense that it allows also to test equivalence with queries of a given path-width, it also covers the previously known result for $k=1$, and it allows to test for equivalence of whether a (one-way) UCRPQ is equivalent to a UCRPQ of a given tree-width (or path-width).<\/jats:p>","DOI":"10.46298\/lmcs-21(1:21)2025","type":"journal-article","created":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T09:55:07Z","timestamp":1741168507000},"source":"Crossref","is-referenced-by-count":1,"title":["Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries"],"prefix":"10.46298","volume":"Volume 21, Issue 1","author":[{"given":"Diego","family":"Figueira","sequence":"first","affiliation":[]},{"given":"R\u00e9mi","family":"Morvan","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2025,3,5]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/15319\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/15319\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T09:55:07Z","timestamp":1741168507000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/12567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,5]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-21(1:21)2025","relation":{"has-preprint":[{"id-type":"arxiv","id":"2212.01679v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2212.01679v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2212.01679","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2212.01679","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2025,3,5]]},"article-number":"12567"}}