Nathanaël Fijalkow
I am a computer scientist working on program synthesis, games, and automata.
program synthesis
games
automata
Get in touch nathanael.fijalkow@gmail.com
Research topics
My habilitation, published in Feb 2022, is a good introduction to my research: it's 20 pages and non-technical. Click here
Games on graphs is at the intersection of several fields: verification (model-checking games such as parity games), logic and model theory (Ehrenfeucht–Fraïssé games), automata theory (emptiness and acceptance games), reinforcement learning (Markov decision processes), and optimisation (mean payoff and discounted games).
Representative work in this topic:
Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives. Marius Belly and Nathanaël Fijalkow and Hugo Gimbert and Florian Horn and Guillermo A. Pérez and Pierre Vandenhove. AAAI Conference on Artificial Intelligence, AAAI (outstanding paper award). 2025
The conception of computer programs is a complicated, costly, and error-prone task. Program synthesis is an ideal where the program is automatically generated from its specification. I am particularly interested in inductive synthesis, also called programming by example, where the specification consists of a set of examples.
Representative work in this topic:
Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis. Théo Matricon and Nathanaël Fijalkow and Guillaume Lagarde. AAAI Conference on Artificial Intelligence, AAAI (invited for oral presentation). 2025
Temporal logics, and in particular Linear Temporal Logic (LTL), are widely used as specification formalisms. I'm interested in ways to learn LTL formulas from traces.
Representative work in this topic:
LTL learning on GPUs. Mojtaba Valizadeh and Nathanaël Fijalkow and Martin Berger. International Conference on Computer Aided Verification, CAV. 2024
A dynamical system follows the evolution of a point through repeated applications of a function; the special case of linear dynamical systems is concerned with linear functions, i.e. multiplication by a matrix. Their algorithmic study is deeply intertwined with deep insights from algebraic number theory and geometry. I am particularly interested in invariants for linear dynamical systems, and in related control problems.
Representative work in this topic:
On the Monniaux Problem in Abstract Interpretation. Nathanaël Fijalkow and Engel Lefaucheux and Pierre Ohlmann and Joël Ouaknine and Amaury Pouly and James Worrell. Journal of the ACM, JACM. 2024
The study of probabilistic automata, in particular algorithms for learning them, has many applications, including natural language processing, modelling of biological systems, and machine learning.
Representative work in this topic:
Consistent Unsupervised Estimators for Anchored PCFGs. Alexander Clark and Nathanaël Fijalkow. Transactions of the Association for Computational Linguistics, TACL. 2020
I'm broadly interested in automata theory, with applications to program verification and reactive synthesis.
Representative work in this topic:
From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History-)Determinism. Antonio Casares and Thomas Colcombet and Nathanaël Fijalkow and Karoliina Lehtinen. TheoretiCS. 2024
Short bio
See the Synthesis team's website
I am a senior researcher at CNRS in LaBRI, Bordeaux (directeur de recherche) where I lead the Synthesis team.
Games on Graphs
Our book, Games on Graphs: From Logic and Automata to Algorithms, has officially been released!
Written by a collective of leading experts, the book was designed to be the definitive modern reference for the field. We’ve worked hard to ensure it is as accessible to students as it is useful for researchers.
You can find the hardback edition at Cambridge University Press, and for those who prefer a digital version, the full content is also available on ArXiv.
Recent publications
For recent slides and lecture notes see below
TACAS 2026: LTLf Learning Meets Boolean Set Cover
This paper sets a new state of the art for LTL learning leveraging Boolean Set Cover
GPU accelerated program synthesis: Enumerate semantics, not syntax!
This paper introduces our recent line of work on GPU accelerated program synthesis to a wide (CS) audience
FMSD 2025: Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic
Journal version of the TACAS 2022 paper, published in Formal Methods in System Design
ICALP 2025: The Trichotomy of Regular Property Testing
We prove that every regular language is either trivial, easy, or hard for property testing.
AAAI 2025: Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives
We construct algorithms for a class of POMDPs based on the idea that information is often and almost-surely revealed.
Received an outstanding paper award!
AAAI 2025: Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis
In this work we construct the first best-first search algorithm with constant delay.
Invited for oral presentation (20% of accepted papers)!
Journal of the ACM 2024: On the Monniaux Problem in Abstract Interpretation
This paper shows decidability and undecidability results for finding semilinear invariants in linear dynamical systems.
CAV 2024: LTL learning on GPUs
This paper constructs an algorithm for learning LTL leveraging the power of GPUs achieving major improvements over the state of the art!
TheoretiCS 2024: From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History-)Determinism
This journal paper constructs optimal transformations between automata over infinite words
Popularization / medias
Mostly in French, see also my media profile by University of Bordeaux
France Culture, CQFD : IA agentique : l'agent trouble
Emission CQFD à France Culture le 26 mars 2026
La Recherche : Quand les agents LLM passent à l'action
Publié en décembre 2025
AI Hub: Making optimal decisions without having all the cards in hand
Published in June 2025
Blog Binaire : Prendre des décisions optimales sans avoir toutes les cartes en main, 2/2 : la science des révélations
Publié en mai 2025
Blog Binaire : Prendre des décisions optimales sans avoir toutes les cartes en main, 1/2 : la genèse d’un papier scientifique
Publié en mai 2025
INS2I : Stratégies optimales : des chercheurs primés lors de la prestigieuse conférence AAAI 2025
Publié en mars 2025
La Recherche : DeepSeek: quand une IA découvre comment raisonner
Publié en mars 2025
La Recherche : L’IA dans la synthèse de programmes
Publié en mai 2024
Ongoing projects
PIQ: GPU-accelerated ARC
Solving ARC-3 with GPU acceleration and program synthesis
ANR ZADyG
ANR project led by Marianne Akian to work on stochastic games
ANR Shannon meets Cray
ANR project led by Charles Paperman to work on automatic program vectorization.
International Research Project (IRP): Le Trójkąt
France / Poland collaboration project between Bordeaux, Paris, and Warsaw
LLM4Code INRIA Challenge
PEPR IA SAIF
SAIF: Safe AI through Formal Methods
More or less recent talks
Seminar Talk: A deep dive into AI coding agents
Not-so-technical talk on how AI coding agents are built
Académie de Médecine: An explainable diagnostic framework for neurodegenerative dementias
Presented in the IA and Healthcare working group on 3 March 2026
POPL 2026 Tutorial: Is Program Synthesis soluble in Large Language Models?
POPL 2024 Tutorial: Machine Learning Meets Program Synthesis
Older versions: PFIA 2024, FM 2023, ECAI 2020
Seminar Talk: LTL learning
This version was given in GREYC, Caen, France on 16/01/2024. Many previous versions were given in many different places...
Habilitation defense
I defended my habilitation on 11 Feb 2022
Current and former members of the Synthesis team
Gabriel Bathie
Postdoc, 2026 -- Present
Arka Ghosh
Postdoc, 2024 -- Present
Roman Kniazev
Postdoc, 2024 -- Present
Priscilla Tissot
Engineer, Jan. 2025 -- Jan. 2026
Baptiste Mouillon
Engineer, Sept. 2024 -- Oct. 2025
Rémi Morvan
PhD, defended on 3 July 2025
Théo Matricon
PhD, defended on 12 Dec. 2024
Pierre Vandenhove
Postdoc, Oct. 2023 -- Sept. 2024
Gaëtan Margueritte
Engineer, Nov. 2023 -- April 2024
Antonio Casares
PhD, defended on 23 Nov. 2023
Ritam Raha
PhD, defended on 5 Sept. 2023
Pierre Ohlmann
PhD, defended on 13 Dec. 2021
Guillaume Lagarde
Postdoc, Sept. 2019 -- Aug. 2021