Contact : seminar@lacl.fr

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

**Daniele Varacca** (LACL)

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

Abstract to be updated

**Olivier Serre** (LIAFA)

** Title to be updated **

Abstract to be updated

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