• English
  • français

  • English
  • français


Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

Séminaires 2015-16


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

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