Games automata play

Posts by categories

  • Learning theory

      March 26, 2019

      Weighted automata and matrix factorisations

      We discuss extensions of Fliess' theorem which says that the smallest weighted automaton for a function is exactly the rank of its Hankel matrix.The goal is to extend this theorem to subclasses of weighted automata such as probabilistic automata.M...

      March 26, 2019

      PAC-learning and compression schemes

      We state and prove the equivalence between PAC-learnability, finite VC dimension, and the existence of compression schemes.Many thanks to Borja Balle, Pascale Gourdeau, and Pierre Ohlmann, for discussions on compression schemes and for the joint e...

      April 13, 2018

      Angluin's style learning for weighted automata

      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 02, 2018

      The fundamental theorem of statistical learning

      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

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

  • Weighted automata

      April 06, 2019

      A polynomial time algorithm for the equivalence problem of weighted automata

      We present an algebraic algorithm solving the equivalence problem for weighted automata (in particular probabilistic automata) in polynomial time.A formal series (here over the reals) is a function .For recognising formal series we use weighted au...

      March 26, 2019

      Weighted automata and matrix factorisations

      We discuss extensions of Fliess' theorem which says that the smallest weighted automaton for a function is exactly the rank of its Hankel matrix.The goal is to extend this theorem to subclasses of weighted automata such as probabilistic automata.M...

      October 19, 2018

      Minimising weighted tree automata and context-free grammars

      We discuss an extension of Fliess' theorem for minimising weighted tree automata.This post is somehow a follow-up of this one, but it can be read independently.Minimising weighted tree automataWe consider tree formal series (here over the reals), ...

      September 04, 2018

      A robust class of sequences

      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

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

      April 13, 2018

      Angluin's style learning for weighted automata

      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

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

  • Parity games

      March 25, 2019

      Strong and weak separating automata

      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

      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

      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

      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

      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

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

      August 10, 2018

      Value iteration for parity games

      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 03, 2018

      Universal trees

      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 02, 2018

      Positional determinacy for parity games, a forward approach

      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

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

  • Games

      August 03, 2018

      Generalized reachability games

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

  • Automata

      August 08, 2018

      The universality problem for automata with bounded ambiguity

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