Showing cs.LOShow all
3 papers · 1 filter
cs.LO2026
A Dichotomy Theorem for Automatic Structures
Antoine Cuvelier, Rémi Morvan
The field of constraint satisfaction problems (CSPs) studies homomorphism problems between relational structures where the target structure is fixed. Classifying the complexity of…
cs.LO2025
Homomorphism Problems in Graph Databases and Automatic Structures
Rémi Morvan
This thesis investigates the central role of homomorphism problems (structure-preserving maps) in two complementary domains: database querying over finite, graph-shaped data, and c…
cs.LO2025
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 is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way naviga…