# Recent Posts

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

• December 27, 2017

### The backward approach of Muller and Schupp for positional determinacy

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

• December 25, 2017

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

• November 10, 2017

### Separation for parity games

Nathanaël Fijalkow

The postulate is that three algorithms for parity games, namely the small progress measure algorithm of Jurdziński, the succinct progress measure algorithm of Jurdziński and Lazić,and the power counting algorithm of Calude et al, ca...