Games automata play

Recent Posts

  • September 04, 2018

    A robust class of sequences

    Corentin Barloy and Nathanaël Fijalkow

    We introduce a subclass of linear recurrent sequences (LRS).We show that this class is robust by giving several characterizations, and tractable by showing that the Skolem and positivity problems are decidable.The results presented here are mostly...

  • 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 whetherThe universality problem is PSP...

  • August 03, 2018

    Universal trees

    Nathanaël Fijalkow

    This post introduces the notion of universal trees and poses an open problem:what is the exact size of the smallest universal tree?The motivation for studying universal trees comes from parity games. This post does not explain this connection at a...

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

  • August 02, 2018

    Positional determinacy for parity games, a forward approach

    Nathanaël Fijalkow

    This post gives a proof of positional determinacy for parity games.One may recognise it in the works of Emerson and Jutla (91) using modal mu-calculus, and also more explicitely in the works of Kupferman and Vardi (98).We fix some notations. Consi...

  • August 02, 2018

    Positional determinacy for parity games, a backward approach by Muller and Schupp

    Nathanaël Fijalkow

    This post revisits Muller and Schupp's backward approach to prove the positionality of parity games.The argument is simple and beautiful; credits go to Thomas Colcombet for this presentation.We discussed the technical details of the construction i...

  • April 13, 2018

    Angluin's style learning for weighted automata

    Nathanaël Fijalkow

    We show that weighted automata over the reals can be learned efficiently in Angluin's supervised scenario.This post uses all the notations of the previous post,and the result presented here was proved in this paper.The scenario is Angluin’s style ...

  • April 12, 2018

    Fliess' theorem for minimising weighted automata

    Nathanaël Fijalkow

    We state and prove Fliess' theorem, which says that the minimal automaton recognising a given formal series has size the rank of its Hankel matrix.A formal series (here over the reals) is a function .The Hankel matrix of is a bi-infinite matrix ...

  • April 02, 2018

    The fundamental theorem of statistical learning

    Nathanaël Fijalkow

    We state and prove the fundamental theorem of statistical learning, which says that a class of functions is learnableif and only if it has finite VC dimension.This post uses all the notations of the previous post. Theorem: If $H$ has infinit...

  • March 15, 2018

    VC dimension, Rademacher complexity, and growth function

    Nathanaël Fijalkow

    We define the VC dimension, the Rademacher complexity, and the growth function of a class of functions.Let $X$ be the set of inputs. The general learning question we consider is the following: we want to learn a target function through a number o...