Nathanaël Fijalkow

I am a computer scientist working on program synthesis, games, and automata.

CV

program synthesis

games

automata

Program Synthesis
Program Synthesis

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
Games on Graphs

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

Controller Synthesis
Controller Synthesis

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

Invariants for Linear Dynamical Systems
Invariants for Linear Dynamical Systems

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

Markovian Models
Markovian Models

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

Learning and Control of Probabilistic Automata
Learning and Control of Probabilistic Automata

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

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

Upcoming (or not anymore) events

Ongoing projects

Research Blog

Collection of research notes, short introductions to recent papers, classical results, open problems

Lucky to be working with

Slides and lecture notes