Ph.D. Thesis
My thesis is entitled Homomorphism Problems in Graph Databases and Automatic Structures and was supervised by Diego Figueira and Nathanaël Fijalkow. You can download the latest version here (2025-05-22).
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.
- Mikołaj Bojańczyk (Uniwersytet Warszawski): reviewer & examiner
- Wim Martens (Universität Bayreuth): reviewer & examiner
- Antoine Amarilli (Inria, Lille): examiner
- Balder ten Cate (Universiteit van Amsterdam): examiner
- Bartek Klin (University of Oxford): examiner
- Anca Muscholl (Université de Bordeaux): examiner
- Sophie Tison (Université de Lille): examiner
- Diego Figueira (CNRS, Bordeaux): supervisor
- Nathanaël Fijalkow (CNRS, Bordeaux): co-supervisor