2025/10/08 by Rémi Morvan, Morvan, Rémi
Computer Science · #Advanced Graph Theory Research #Algebra homomorphism #Boolean conjunctive query #Conjunctive query #Data Management and Algorithms #Decidability #Equivalence (formal languages) #Graph #Graph Theory and Algorithms #Graph homomorphism #Homomorphism #Query language #Undecidable problem
paper · pdf · doi:10.48550/arxiv.2510.07422
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/10/08 · openalex created_date 2025/10/16 · openalex updated_date 2026/08/05
This thesis investigates the central role of homomorphism problems (structure-preserving maps) in two complementary domains: database querying over finite, graph-shaped data, and constraint solving over (potentially infinite) structures. Building on the well-known equivalence between conjunctive query evaluation and homomorphism existence, the first part focuses on conjunctive regular path queries, a standard extension of conjunctive queries that incorporates regular-path predicates. We study the fundamental problem of query minimization under two measures: the number of atoms (constraints) and the tree-width of the query graph. In both cases, we prove the problem to be decidable, and provide efficient algorithms for a large fragment of queries used in practice. The second part of the thesis lifts homomorphism problems to automatic structures, which are infinite structures describable by finite automata. We highlight a dichotomy, between homomorphism problems over automatic structures that are decidable in non-deterministic logarithmic space, and those that are undecidable (proving to be the more common case). In contrast to this prevalence of undecidability, we then focus on the language-theoretic properties of these structures, and show, relying on a novel algebraic language theory, that for any well-behaved logic (a pseudovariety), whether an automatic structure can be described in this logic is decidable.