Games automata play

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