Contact : seminar@lacl.fr

Les archives : 2014-15, 2013-14, 2012-13, 2011-12, 2010-11, 2009-10, 2008-09

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

**Christophe Bahadoran** (

** Titre à venir **

Résumé à venir

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

**Alexis Bès** (LACL)

** Title to be updated **

Abstract to be updated

**Sebastian Barbieri** (ENS-Lyon)

** The domino problem for structures between Z and Z^d **

**Daniele Varacca** (LACL)

** On the Buridan’s Principle by Leslie Lamport **

Abstract to be updated

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

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

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

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

**Mehdi Haddad** (LACL)

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

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

**Benoît Barbot** (LACL - UPEC)

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

LACL, Département d'Informatique |
Flore Tsila |
Régine Laleau |