# Séminaire

## Séminaires 2015-16

### 2016-02-01

Olivier Serre (LIAFA)

How Good Is a Strategy in a Game With Nature?

We consider games with two antagonistic players — Éloïse (modelling a program) and Abélard (modelling a byzantine environment) — and a third, unpredictable and uncontrollable player, that we call Nature. Motivated by the fact that the usual probabilistic semantics very quickly leads to undecidability when considering either infinite game graphs or imperfect information, we propose two alternative semantics that leads to decidability where the probabilistic one fails: one based on counting and one based on topology.

Titre à venir

Résumé à venir

### 2016-01-18

Edon Kelmendi (LaBRI)

Limit-sure reachability in a class of stochastic semiperfect-information games

We study two-player stochastic games with reachability conditions where the maximizer has no information whereas the minimizer has perfect-information. The question of limit-sure reachability is the following: is it true that for all epsilon>0 and finite-memory strategies tau (for the minimizer) there exists a finite word w (for the maximizer) such that the probability of reaching the final states is larger than 1-epsilon when the game unravels according to w and tau. This question is undecidable in general, the reason being that if the minimizer has no choice at all such a game is equivalent to a probabilistic finite automaton where the value 1 problem is undecidable. Building up on previous work on probabilistic finite automata we identify a robust class of games where the limit-sure reachability is decidable. We also show that there are games where the optimal strategies of the minimizer need infinite-memory which is slightly surprising since the minimizer has perfect-information.

### 2015-12-07

Alexis Bès (LACL)

Title to be updated

Abstract to be updated

### 2015-11-30

Sebastian Barbieri (ENS-Lyon)

The domino problem for structures between Z and Z^d

We define the domino problem for subshifts where the symbols are restrained to subsets of Z^d. More specifically, we focus on subsets which have a self-similar structure defined by a family of substitutions. In this setting we exhibit non-trivial families of structures where the domino problem is decidable and undecidable. Amongst those we show that the Sierpinski triangle has decidable domino problem, while the Sierpinski carpet has undecidabe domino problem.

### 2015-11-23

Daniele Varacca (LACL)

On the Buridan’s Principle by Leslie Lamport

Abstract to be updated

### 2015-11-09

Nicolas Markey (LSV, ENS Cachan)

ATL with strategy contexts

The alternating-time temporal logic (ATL) was defined 15 years ago as an extension of CTL for expressing and verifying properties of multi-player games. However, in order to inherit nice algorithmic properties of CTL, ATL has limited expressiveness. In this talk, I will begin with presenting our extension of ATL with strategy contexts, which contrary to ATL can express rich properties with interactions between strategies. I will then present QCTL, the extension of CTL with quantification over atomic propositions, and explain how it can be used to get algorithms for ATL with strategy contexts. This talk is based on joint works with Thomas Brihaye, Arnaud Da Costa Lopes, and François Laroussinie.

### 2015-11-02

Andreï Romashchenko (LIRMM, Montpellier)

Quasiperiodicity and non-computability in tilings.

We study tilings of the plane that combine strong properties of different nature: combinatorial and algorithmic. We prove the existence of a tile set that accepts only quasiperiodic and non-recursive tilings. We characterise the classes of Turing degrees that can be represented by quasiperiodic tilings. We also show that every minimal 1-dim subshift can be implemented as a subaction of a 2-dim minimal SFT.

### 2015-10-12

Reem Yassawi (

Décidabilité de la conjugaison topologique entre shifts substitutifs de longueur constante

Soit $(X,\sigma)$ et $(Y,\sigma)$ deux shifts: une conjugaison (topologique) entre ces deux systèmes est un homéomorphisme $\Phi:X\rightarrow Y$ qui commute avec le shift. Autrement dit, une conjugaison est un automate cellulaire bijectif entre X et Y. Étant donné deux shifts, nous voudrions savoir s'il existe une conjugaison entre eux. Nous démontrons que si $(X,\sigma)$ et $(Y,\sigma)$ sont engendrés par des substitutions de longueurs constantes, alors il y a un algorithme qui énumère toutes les conjugaisons entre ces deux systèmes. Ceci est un travail commun avec Ethan Coven et Anthony Quas.

### 2015-10-05

Mathieu Sassolas (LACL)

Polynomial Interrupt Timed Automata

Modeling real world systems implies taking into account the continuous elapsing of time along with the discrete set of states the system can operate in, thus yielding so called /hybrid systems/. However, verification of such systems is mostly undecidable, and finding decidable fragments has been an ongoing research topic for the last 25 years. In this work we propose a decidable model of hybrid systems taking into account constraints expressed by polynomials instead of the more widespread linear constraints. The decision procedure relies on the cylindrical decomposition of reals.

This talk is based on joint work with Béatrice Bérard, Serge Haddad, Claudine Picaronny, and Mohab Safey El Din.

### 2015-09-28

Inference of sensitive information in data integration systems

The inference problem, in an access control context, refers to the ability of a malicious user to synthesize sensitive information from a combination of non sensitive information. This problem is highlighted in data integration systems where a mediator providing a unique entry point to several heterogeneous sources is defined.

In this talk we describe an incremental methodology able to tackle the inference problem in a data integration context. This methodology has three phases. The first phase, the propagation phase, allows combining source policies and therefore generating a preliminary policy at the mediator level. The second phase, the detection phase, characterizes the role of semantic constraints in inducing inference about sensitive information. We also introduce in this phase a graph-based approach able to enumerate all indirect access that could induce accessing sensitive information. In order to deal with previously detected indirect access, we introduce the reconfiguration phase which provides two solutions. The first solution could be implemented at design time. The second solution could be implemented at runtime.

### 2015-09-21

Benoit Monin (UPEC LACL)

A small history of K-triviality

The Kolmogorov complexity of a string is, informally, the length of the smallest program that produces this string. We write C(\s) = n to mean that the smallest program producing the string \s is of length n.

An infinite binary sequence X is said to be C-trivial if the Kolmogorov complexity of its prefixes is minimal, that is, if there is a constant d such that for any n, we have C(X \rest n) < C(n) + d (Here X \rest n denotes the n first bits of X). It is clear that any computable (infinite binary) sequence is C-trivial. Chaitin proved that the converse holds:

A sequence X is computable iff it is C-trivial (1).

Chaitin also successfully used Kolmogorov complexity to provide a formal definition of the intuitive idea we can have of a random sequence. To do so, he needed a variation of the standard Kolmogorov complexity, called “prefix Kolmogorov complexity” and denoted by K. Using this prefix Kolmorogov complexity K, he defined a sequence Z to be random if for any n we have K(Z \rest n) > n - d for some constant d. The intuition is that the prefix Kolmogorov complexity should be maximal for prefixes of random sequences. This definition of randomness is still today the most studied, for many reasons that we shall not detail during the talk.

Chaitin conjectured (1) to also be true with prefix Kolmorogov complexity K, that is, X is computable iff X is K-trivial (that is, there is d such that for every n we have K(X \rest n) < K(n) + d). Solovay later refuted the conjecture by constructing a non-computable K-trivial sequence A. The notion of K-triviality was born, and had yet to reveal many surprises through its numerous different characterizations, and its connections with algorthmic randomness.

After introducing the main concepts with more details, we will try during this talk to give some explanations and intuitions on the work that has been done by various people on K-triviality these last 15 years.

### 2015-09-14

Benoît Barbot (LACL - UPEC)

Building Power Consumption Models from Executable Timed I/O Automata Specifications

We develop a novel model-based hardware-in-the-loop (HIL) framework for optimising energy consumption of embedded software. Software components are specified as networks of parameterised timed input/output automata, which are translated into executable code run on a microcontroller connected to an executable plant model and a power monitor. We use timed Petri nets as an intermediate representation of the executable specification, which facilitates efficient code generation and fast simulations. The framework is able to produce optimal values of timing parameters that minimise energy usage, without compromising a given safety requirement, together with a probabilistic power consumption model derived from real measurement data. Our framework uniquely combines the advantages of rigorous distributed real-time specifications with accurate power measurements and online power model construction.

 Adresse : LACL, Département d'Informatique Faculté des Sciences et Technologie 61 avenue du Général de Gaulle 94010 Créteil Cedex Secrétariat : Flore Tsila Bâtiment P2 - 2ème étage - bureau 215 Tél : +33 (0)1 45 17 16 47 Fax : +33 (0)1 45 17 66 01 Direction : Régine Laleau Bâtiment P2 - 2ème étage - bureau 208 Tél : +33 (0)1 45 17 65 97 Fax : +33 (0)1 45 17 66 01