2 citations · 3 across the 7 of their papers we have counts for
9 papers
A Dichotomy Theorem for Homomorphism Problems on 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…
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…
Separating Automatic Relations
Pablo Barceló, Diego Figueira, Rémi Morvan
We study the separability problem for automatic relations (i.e., relations on finite words definable by synchronous automata) in terms of recognizable relations (i.e., finite union…
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…