PhD Thesis

General Information

My thesis, Homomorphism Problems in Graph Databases and Automatic Structures, focuses on optimizing graph database queries and studying constraint satisfaction problems over automatic structures. I was supervised by Diego Figueira and Nathanaël Fijalkow, at LaBRI, Université de Bordeaux, from September 2021 to August 2025.

Abstract. 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.

Composition of the jury.

Defence

My defence took place on Thursday, 3rd July 2025 in LaBRI’s amphitheatre (Bâtiment A27, Domaine universitaire, 351 cours de la Libération, 33405 Talence).

Recordings

Program