Research Posts

January 18, 2022
L'avènement de la synthèse de programme
Nathanaël Fijalkow
Article à paraître dans IntersticesLa notion de programme est au centre de l'informatique : c'est l'intermédiaire entre l'utilisateur et la machine, le moyen par lequel un humain peut communiquer à la machine des opérations à effectuer pour réalis...
December 02, 2019
Populations of Markov decision processes, what we know and an open question
Nathanaël Fijalkow
We present the model of populations of Markov decision processes, discuss our recent result on this model, and show an intriguing open question.The adversarial settingThe model of populations of Markov decision processes is directly inspired by th...
November 11, 2019
DeepCoder, Learning to write programs
Nathanaël Fijalkow
This post is a short presentation of the DeepCoder paper, which proposed in 2017 a very interesting line of attack for improving program synthesis using machine learning.The DeepCoder paper can be found here. It is a great source of inspiration fo...
November 10, 2019
The complexity of solving games with combination of objectives
Ashwani Anand and Nathanaël Fijalkow
We investigate the use of separation automata (or equivalently, universal graphs) for combination of objectives.The general idea is to find ways of combining the solutions for each of the objective into one for the combination, as much as possible...
September 23, 2019
Applying to CNRS
Nathanaël Fijalkow
This post gathers some information about applying to CNRS for a permanent researcher position (chargé de recherche, junior position, or directeur de recherche, senior position).It includes links to my files for the two times I applied.Disclaimer: ...
September 22, 2019
Why we should turn to journals
Nathanaël Fijalkow
Why do I avoid submitting to highly selective conferences?What do I mean by highly selective conferences? I refer to the publication system which consists in regular (often yearly) events where researchers submit “extended abstracts” of their late...
September 01, 2019
Parity games, the quasipolynomial era
Nathanaël Fijalkow
This post is an overview on my recent research related to the quasipolynomial time algorithms for parity games.It can serve as a roadmap for various posts on this blog.Another piece of material for these results is the slides for my invited talk a...
April 06, 2019
A polynomial time algorithm for the equivalence problem of weighted automata over a field
Nathanaël Fijalkow
We present an algebraic algorithm solving the equivalence problem for weighted automata over a field (in particular probabilistic automata) in polynomial time.Edits29/03/2020: Clarified the model to avoid a terminology clashWe consider weighted au...
March 25, 2019
Strong and weak separating automata
Nathanaël Fijalkow
This post discusses the difference between strong and weak separating automata.The goal of this post is to discuss the notion of separating automata, which already appear in many previous posts, see this post and this post for parity games,this po...
February 10, 2019
Mean payoff games and universal graphs
Nathanaël Fijalkow
This post discusses using separating automata for constructing algorithms for solving mean payoff games.The goal of this post is to present the main results of this paper,meaning upper and lower bounds on separating automata for mean payoff games....
February 09, 2019
Separating automata and universal graphs
Nathanaël Fijalkow
This post discusses the equivalence between separating automata and universal graphs beyond parity games.The goal of this post is to present again the result of this paper, which is a joint work with Thomas Colcombet, but this time in more general...
October 12, 2018
Parity games and universal graphs
Nathanaël Fijalkow
This post introduces the notion of universal graphs and their applications to parity games.The goal of this post is to prove the main result of this paper,meaning that separating automata have at least quasipolynomial size.This quasipolynomial bar...
October 11, 2018
The fundamental theorem of parity games
Nathanaël Fijalkow
This post proves a very important theorem about parity games, showing the interplay with (universal) trees.The goal of this post is to prove the following result.This is the key technical point of a recent joint work with Thomas Colcombet proving ...
October 10, 2018
Separation for parity games
Nathanaël Fijalkow
This post discusses a framework for reducing parity games to safety games by the construction of an automaton.There are three quasipolynomial time algorithms for parity games, namely the statistics games of Calude, Jain, Khoussainov, Li, and Steph...
September 04, 2018
A robust class of sequences
Corentin Barloy and Nathanaël Fijalkow
We introduce a subclass of linear recurrence sequences (LRS).We show that this class is robust by giving several characterisations.The results presented here are mostly due to Corentin Barloy, who took a summer internship in LaBRI, Bordeaux, under...
August 15, 2018
Boundedness for (min,plus)-automata
Nathanaël Fijalkow
We prove that the boundedness problem for (min,plus)-automata is decidable.One of the main application of this result is that the star-heigh problem of regular expressions reduces to (a slight extension of) it.The main point is to present a very u...
August 10, 2018
Value iteration for parity games
Nathanaël Fijalkow
This post presents a generic value iteration algorithm for parity gamesparametrised by universal trees. As special cases this extends the small progress measure of Jurdziński and the succinct progress measure of Jurdziński and Lazić...
August 08, 2018
The universality problem for automata with bounded ambiguity
Ritam Raha and Nathanaël Fijalkow
We prove that the universality problem for automata with fixed ambiguity is decidable in polynomial time.Given an automaton $\A$ on alphabet $A$ recognising the language $L(\A)$, the universality problem asks whether\[\forall w \in A^*, w \in L(\A...
August 03, 2018
Universal trees
Nathanaël Fijalkow
This post introduces the notion of universal trees, and shows upper and lower bounds.The bounds are almost matching, leaving an open problem: what is the exact size of the smallest universal tree?The motivation for studying universal trees comes f...
August 03, 2018
Generalized reachability games
Nathanaël Fijalkow
This post is about generalized reachability games. The main purpose is to pose an open problem:what is the complexity of solving 2-generalized reachability games?This post is about this paper. This is the first research paper I have worked on (wit...