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, where the specification consists of a set of examples.

Reactive synthesis is the special case of program synthesis where the program takes actions over time in a partially controllable environment. I focus on temporal synthesis, where the specification is given by a logical formula in linear temporal logic (LTL) and its extensions.

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

Markovian models are stochastic models with memoryless dynamics. The distinction with probabilistic automata is that Markovian models such as Markov decision processes are fully observable.

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.

The study of probabilistic automata, in particular algorithms for learning and controlling them, has many applications, including program verification, natural language processing, modelling of biological systems, and machine learning.
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.
Chat TGV
What would happen if Chat TGV could reason, cite, justify?
Recent works
How to Play Optimally for Regular Objectives?
Our latest games paper was accepted to ICALP: International Colloquium on Automata, Languages, and Programming. It's about characterising the amount of memory required for regular objectives. Joint work with Patricia Bouyer, Mickael Randour, and Pierre Vandenhove.
WikiCoder: Learning to Write Knowledge-Powered Code
Our latest program synthesis paper got accepted in SPIN: International Symposium on Model Checking of Software. It's about combining ChatGPT, or other large language models tools for program synthesis, with knowledge graphs to get your facts straight! Joint work with Théo Matricon.
DeepSynth: Scaling Neural Program Synthesis with Distribution-based Search
DeepSynth is a general-purpose program synthesizer in the programming by example framework: the user provides a few examples as pairs of input and output, DeepSynth finds a program matching the examples.
The software is published in the Journal of Open Source Software and is heavily used in our recent papers for experiments, starting from our AAAI 2022 paper.
News
Tutorial on Machine Learning guided Program Synthesis
I gave a half-day tutorial at FM (The International Symposium on Formal Methods) on 6 March 2023. Handwritten slides: Intro Part I: Machine Learning Part II: Programming languages Part III: Algorithms Perspectives. Accompanying tool: DeepSynth
Guillaume Lagarde joining our group
Guillaume Lagarde is joining our research group (M2F) in LaBRI, Bordeaux!
PEPR IA SAIF
I am part of the PEPR IA SAIF: Safe AI through Formal Methods, starting in Sept 2023. We have many open positions in LaBRI, please get in touch!
Dagstuhl seminars
I am coorganising two Dagstuhl seminars: The Future of Reactive Synthesis, to be held in September 2023, and Stochastic Games, to be held in June 2024.
Collaboration project between Bordeaux and Warsaw
The International Emerging Actions project WinCent and between LaBRI and University of Warsaw, Poland will run for two years (Jan 2023 -- Dec. 2024). The PIs are Filip Mazowiecki and myself
Invited talk
I am giving a talk at the Workshop on Open Problems in Learning and Verification of Neural Networks (Wolverine), in Paris on July 17, colocated with CAV.
Program Committees
AAAI 2024
AAAI 2024, the International Conference on Artificial Intelligence
VMCAI 2024
VMCAI 2024, the International Conference on Verification, Model Checking, and Abstract Interpretation
DAV 2023
DAV 2023, the International Workshop on Deep Learning-aided Verification
QEST 2023
QEST 2023, the International Conference on Quantitative Evaluation of SysTems
IJCAI 2023
IJCAI 2023, the International Joint Conference on Artificial Intelligence
Research Blog
Collection of research notes, short introductions to recent papers, classical results, open problems
Collaboration
I am a junior researcher at CNRS in LaBRI, Bordeaux (chargé de recherche). I am also a research fellow of The Alan Turing Institute of data science and artificial intelligence in London.
There are many open positions in the PEPR IA Project SAIF: Safe AI through Formal Methods: Please get in touch!
Proud of (non-exhaustive list)
Pierre Ohlmann
- CNRS position in Marseille!
- CSR best paper award
- single author paper at TheoretiCS
- proven ability to bring universal graphs to any scientific discussion
Antonio Casares
- CSL best student paper (Helena Rasiowa award)
- proven ability to bring the alternating cycle decomposition construction to any scientific discussion
Théo Matricon
Ritam Raha
Rémi Morvan
- grand écart: do you know any PhD student who published on parity games, logic over countable orders, and regular path queries?