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
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:
Scaling Neural Program Synthesis with Distribution-based Search. Nathanaël Fijalkow and Guillaume Lagarde and Théo Matricon and Kevin E. Ellis and Pierre Ohlmann and Akarsh Potta. AAAI Conference on Artificial Intelligence, AAAI. 2022
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:
Games on Graphs. Nathanaël Fijalkow and Nathalie Bertrand and Patricia Bouyer and Romain Brenguier and Arnaud Carayol and John Fearnley and Hugo Gimbert and Florian Horn and Rasmus Ibsen-Jensen and Nicolas Markey and Benjamin Monmege and Petr Novotný and Mickael Randour and Ocan Sankur and Sylvain Schmitz and Olivier Serre and Mateusz Skomra. 2023
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
I am working at Nukkai, a start-up working on Agentic AI, and 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
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!
La Recherche (avril 2024): L’IA dans la synthèse de programmes
In French: popularisation article about AI and program synthesis, published in La Recherche
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.
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
Roman Kniazev (postdoc)
Programmatic reinforcement learning
Arka Ghosh (postdoc)
Automata learning
Théo Matricon (PhD)
Program synthesis
Rémi Morvan (PhD)
Logic and automata theory, database theory
Gabriel Bathie (PhD)
Regular property testing, program synthesis
Baptiste Mouillon (engineer)
LTL learning
Slides and lecture notes
LLM from scratch
This is a notebook created for a course I taught where the goal was to code a whole Transformer from scratch.
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 since 2019
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