一句话：证明对任意 k，判定 UC2RPQ 是否等价于树宽 k 的查询可判定，并给出最大下近似与复杂度。
本文研究带双向导航的合取正则路径查询的并（UC2RPQ）与有界树宽查询的语义关系。此前仅知 k=1 时可判定；作者证明对任意 k≥1，判定一个 UC2RPQ 是否等价于树宽为 k 的查询是可判定的，算法上界为 2ExpSpace。若所有正则表达式限制为 a* 或 (a1+…+an)，复杂度降至 Π^P_2。作者还研究用小树宽查询近似 UC2RPQ，给出对任意固定 k 构造其树宽 k 最大下近似的算法，该近似在包含关系下最大且唯一。方法可扩展至路径宽等价判定，并覆盖 k=1 的已有结果及单向 UCRPQ 的树宽/路径宽等价问题。
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).
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{FigueiraM25,
title = {Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries},
author = {Diego Figueira and Rémi Morvan},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:21)2025}
}