# Research Posts

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