Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries

Diego Figueira, Rémi Morvan

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 naviga…