We focus on stochastic games,
which can model interaction with an adverse environment,
as well as probabilistic behaviour arising from uncertainties.
Our contribution is twofold.
First, we study long-run specifications
expressed as quantitative multi-dimensional
mean-payoff and ratio objectives.
We then develop an algorithm to synthesise epsilon-optimal strategies for conjunctions of almost sure satisfaction for mean payoffs
and ratio rewards (in general games) and Boolean combinations of expected
mean-payoffs (in controllable multi-chain games).
Second, we propose a compositional framework, together with assume-guarantee rules,
which enables winning strategies synthesised for individual components to be composed to a winning strategy for the composed game.
The framework applies to a broad class of properties, which also include expected total rewards,
and has been implemented in the software tool PRISM-games.

It seems that all statisticians know the concept of p-value is but none is willing to explain it. The only reference that we have been able to find is the  1974 book “Theoretical Statistics” by Cox and Hinkley where the authors define the concept, sort of, but do not use the term “p-value.”
We explain the concept presupposing only rudimentary probability theory; we examine the concept and we discuss the use of it.
For simplicity, our explanation is focused on the discrete case with no outcomes of zero probability but we’ll say a few words on the general case as well.
The talk builds on joint work with Vladimir Vovk of the University of London.

Traditionnelement, la théorie de la calculablilité se fait dans l’espace de Cantor : l’espace des suites infinies de 0 et de 1. Cependant, il est possible de définir ce qu’est un élément calculable, une fonction calculable, dans des espaces plus généraux. Cela nous permet par exemple de définir un calcul prenant en entrée un réél sans passer par sa représentation en binaire.
Un de ces espaces, le cube de Hilbert ([0;1]^N), présente la particularité de posséder des éléments qui ne sont calculatoirement équivalents à aucun élément de l’espace de Cantor. Les degrés du cube de Hilbert sont appelés degrés continus.
Dans cette exposé nous allons voir comment un théorème de calculabilité classique s’étend aux degrés continus : le lemme de Schoenfield, qui affirme que X est calculable en le problème de l’arret si et seulement si on peut calculer une suite qui converge vers X.

Considérons l’ensemble des suites de 0 et 1. Nous nous intéressons au sous-ensemble des suites dont les chiffres à la position k et à la position 2k ne sont pas deux 1 pour chaque k. On l’appelle le décalage de Fibonacci multiplicatif. C’est un analogue du décalage de Fibonacci classique qui est l’ensemble des suites qui ne contiennent pas deux 1 consécutifs. Le décalage de Fibonacci multiplicatif a la mesure de Lebesgue zéro. Pour trouver sa « vraie taille », nous calculons ses dimensions fractales : dimensions de Minkowski et de Hausdorff. Les deux dimensions sont différentes : la première est donnée par une série numérique concernant la suite de Fibonacci et la seconde est une solution d’une équation algébrique.

L’entropie topologique d’un système dynamique est un paramètre réel qui mesure sa complexité dynamique. J’étudie ici deux questions liées: quelle valeur peut prendre ce paramètre, et peut-on le calculer (algorithmiquement) ?

Dans les sous-shifts ou pavages de type fini (SFT) en dimension 1, on sait la calculer depuis 30 ans, et la méthode utilisée nous permet de caractériser l’ensemble des entropies possibles par une condition algébrique. En dimension supérieure, la surprise est venue en 2007 : non seulement l’entropie n’est pas calculable, mais l’ensemble des réels semi-calculables par le haut apparaissent comme entropies possibles. C’est le premier d’une série de résultats de “réalisation” qui s’est depuis décliné sur de nombreux autres objets.

Sous des hypothèses supplémentaires, par exemple de fortes conditions de mélange, l’entropie redevient calculable; les entropies possibles sont alors caractérisées par des conditions de calculabilité plus fortes. Les hypothèses “minimales” de ce résultat ne sont pas encore bien comprises.

Dans cet exposé, j’explore le cas des sous-shifts ou pavages généraux, i.e. pas de type fini. Je met en relation la difficulté de décider si un motif apparait dans le pavage et la difficulté de calculer la valeur de l’entropie. J’exhibe un saut de difficulté qui est fonction du taux de mélange, le problème devenant brusquement plus difficile au-delà d’une valeur seuil.

Ce travail est une collaboration avec Silvère Gangloff, Mathieu Sablik et Cristobal Rojas.

Un jeu de tuiles de Wang est un ensemble fini de carrés unités dont
on a colorié chaque côté. Un jeu de tuiles T pave le plan si celui-ci peut
être recouvert par des translatés de copies d'éléments de T (selon Z^2), de
sorte que les arêtes en contact de deux tuiles adjacentes soient de même
couleur. Un jeu de tuiles est dit apériodique s'il pave le plan mais si
aucun pavage obtenu n'est invariant par une translation. La plupart des jeux
de tuiles apériodiques sont construits de façon autosimilaire (via une règle
de substitution).

Nous avons introduit deux invariants permettant de quantifier le niveau
d'apériodicité d'un jeu de tuiles de Wang. L'un des invariants est de nature
topologique, l'autre est métrique. Nous nous attarderons sur le premier, qui
consiste a paver de grandes surfaces (dites "de translation") tout en
minimisant leur genre.