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 junior researcher at CNRS in LaBRI, Bordeaux (chargé de recherche) where I lead the Synthesis team.
I am looking for interns, PhD students, and postdocs to work on different projects (see below). Please get in touch!
Games on Graphs
The Games on Graphs book is online (and free)! It's a collaborative textbook on Games on Graphs: 490 pages, 13 chapters, 17 authors, and even more monkeys. A printed version will be published in 2024 by Cambridge University Press!
Recent publications
For recent slides and lecture notes see below
ICALP 2025: The Trichotomy of Regular Property Testing
We prove that every regular language is either trivial, easy, or hard to test 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
JOSS 2024: Scarlet: Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic
This software, published in the Journal of Open Source Software (JOSS), is a state of the art tool for learning (fragments of) LTL
LMCS 2024: Playing Safe, Ten Years Later
This journal paper, published 10 years after the conference version, gives an updated view on this now widely extended result characterising the memory requirements for topologically closed objectives.
Popularization / medias
Mostly in French, see also my media profile by University of Bordeaux
Mars 2025, INS2I : stratégies optimales : des chercheurs primés lors de la prestigieuse conférence AAAI 2025
L'Institut Informatique du CNRS présente notre article
Mars 2025, La Recherche : DeepSeek: quand une IA découvre comment raisonner
In French: popularisation article about DeepSeek, published in La Recherche
Mai 2024, La Recherche : L’IA dans la synthèse de programmes
In French: popularisation article about AI and program synthesis, published in La Recherche
Mars 2022, Interstices : L’avènement de la synthèse de programme
In French: popularisation article about AI and program synthesis, published in Interstices
Upcoming (or not anymore) events
Workshop on Trustworthy AI
I am coorganising a workshop on the Theoretical Aspects of Trustworthy AI, to be held at the Simons Institute for the Theory of Computing in Berkeley the week April 28 -- May 2nd 2025
Program Synthesis days
I am coorganising a two-days workshop on Program Synthesis on 26/27 Nov 2024 in LaBRI, Bordeaux
Synthesis seminar series
We organise more or less regularly seminar talks in the synthesis team
Ongoing projects
ANR Shannon meets Cray
ANR project led by Charles Paperman to work on automatic program vectorization.
International Research Project (IRP) between Bordeaux, Paris, and Warsaw
Le Trójkąt is a France / Poland collaboration project.
Jan 2024 -- Dec. 2028
LLM4Code INRIA Challenge
Started in 2024
PEPR IA SAIF
SAIF: Safe AI through Formal Methods
PNRIA Tarski LLM
Working with CNRS PNRIA engineers and the supercomputer Jean-Zay on Tarski LLMs for generating bottom-up code
Research Blog
Collection of research notes, short introductions to recent papers, classical results, open problems
Value iteration for parity games
Upper and lower bounds for universal trees
The interplay between parity games and universal trees
Lucky to be working with
Gabriel Bathie (PhD)
Regular property testing, program synthesis
Arka Ghosh (postdoc)
Automata learning
Roman Kniazev (postdoc)
Programmatic reinforcement learning
Baptiste Mouillon (engineer)
LTL learning
Rémi Morvan (PhD)
Logic and automata theory, database theory
Priscilla Tissot (engineer)
An agent for University of Bordeaux
Slides and lecture notes
Course on Large Language Models
48 hours course taught at MVA starting 2025.
Tutorial on Machine Learning Meets Program Synthesis
I gave different versions of this tutorial: POPL 2024, FM 2023, ECAI 2020
Seminar talk on LTL learning
This version was given in GREYC, Caen, France on 16/01/2024. Many previous versions were given in many different places...
Course on Infinite duration games on graphs
12 hours course, taught at MPRI 2019 -- 2024
Course on Reinforcement Learning
Taught amongst others in ENSEIRB (engineering school) since 2020, in University of Bordeaux, and at the Alan Turing Institute as a research school.
Habilitation defense
I defended my habilitation on 11 Feb 2022
Presentation of PEPR IA SAIF
This is an informal presentation of the planned activities of PEPR IA SAIF in LaBRI