Logo IRISA      logo Inria

Le séminaire en bref

Le séminaire 68NQRT est un séminaire commun de l'IRISA et d'Inria Rennes. Il a lieu le jeudi à 14 heures par défaut dans la salle Markov. Les thèmes du séminaire recouvrent des thèmes étudiés dans les départements « réseaux, télécommunication et services » et « langage et génie logiciel » de l'IRISA, ou des thèmes « Algorithmique, programmation, logiciels et architectures » et  « Réseaux, systèmes et services, calcul distribué » d'Inria. On y trouve des exposés introductifs, avancés ou prospectifs dans les thèmes du génie logiciel, de l'informatique théorique, des mathématiques discrètes et de l'intelligence artificielle.

D'après Mathematical Subject Classification:
68 Computer Science
N Software
Q Theory of computing
R Discrete mathematics in relation to computer science
T Artificial intelligence

Prochain Exposé

jeudi 3 novembre 14h, en salle Minquiers

Béatrice Bérard

Preserving opacity on Interval Markov Chains under simulation.

Given a probabilistic transition system (PTS) A partially observed by an attacker, and an omega-regular predicate P over the traces of A, measuring the disclosure of the secret P in A means computing the probability that an attacker who observes a run of A can ascertain that its trace belongs to P. We consider specifications given as Interval Markov Chains (IMCs), which are underspecified Markov chains where probabilities on edges are only required to belong to intervals. Scheduling an IMC S produces a concrete implementation as a PTS and we define the worst case disclosure of secret P in S as the maximal disclosure of P over all PTSs thus produced. We compute this value for a subclass of IMCs and we prove that simulation between specifications can only improve the opacity of implementations.

Exposés des semaines suivantes

jeudi 10 novembre, 14h, en salle Aurigny

Uli Schlachter

Reducing Linear Algebra in Petri Net Synthesis.

The goal in Petri net synthesis is to find a Petri net solving a given specification, or to conclude that no such net exists. More specifically, the Petri net should have a reachability graph that is isomorphic to a given labelled transition system. Petri net synthesis is based on region theory, which provides a linear-algebraic characterisation of the class of solvable transition systems by describing so-called separation problems. In this talk we will look at more direct characterisations. A purely graph-theoretical characterisation for 'state separation problems' is presented. This characterisation allows to better understand the substructures in a transition system that make state separation problems unsolvable. Another aspect will be targeted synthesis. For very special classes, such as finite, non-branching labelled transition systems having only two edge labels, linear-algebra-free characterisations can be found. We present an efficient characterisation of this class as a letter-counting criterion. This characterisation leads to a synthesis algorithm with quadratic time complexity.

jeudi 17 novembre, 14h

Thomas Chatain (LSV)

Anti-alignments in Conformance Checking - The Dark Side of Process Models

To Be Anounced

jeudi 1er Décembre, 14h

Serguei Lenglet

Howe's Method for Contextual Semantics.

To Be Anounced