5 papers
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…
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…
Minimizing Conjunctive Regular Path Queries
Diego Figueira, Rémi Morvan, Miguel Romero
We study the minimization problem for Conjunctive Regular Path Queries (CRPQs) and unions of CRPQs (UCRPQs). This is the problem of checking, given a query and a number , whethe…
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…
The Algebras for Automatic Relations
Rémi Morvan
We introduce "synchronous algebras", an algebraic structure tailored to recognize automatic relations (aka. synchronous relations, or regular relations). They are the equivalent of…