L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris-Diderot, qui héberge deux équipes-projets INRIA.

Les recherches menées à l'IRIF reposent sur l’étude et la compréhension des fondements de toute l’informatique, afin d’apporter des solutions innovantes aux défis actuels et futurs des sciences numériques.

L'IRIF regroupe près de deux cents personnes. Six de ses membres ont été lauréats de l'European Research Council (ERC), trois sont membres de l'Institut Universitaire de France (IUF) et deux sont membres de l'Academia Europæa.

(rafraîchir la page pour changer de notion)

Pierluigi Crescenzi

IRIF has the great pleasure to welcome a new professor (Paris Diderot): Pierluigi Crescenzi, an expert in graph algorithms, particularly in the analysis of real-world complex networks.

Claire Mathieu

IRIF has the great pleasure to welcome a new research scientist (CNRS): Claire Mathieu, an expert in algorithms, particularly the design of approximation schemes for NP-hard combinatorial.

ICFP: International Conference On Functional Programming

The paper “Equivalences for Free : Univalent Parametricity for Effective Transport” of Matthieu Sozeau (IRIF), with his coauthors Nicolas Tabareau and Eric Tanter, has been selected as a distinguished paper of the ICFP conference.

Jean-Éric Pin

Jean-Eric Pin, CNRS senior researcher at IRIF, is awarded the Arto Salomaa prize for his outstanding contribution to the field of Automata Theory.


IRIF is seeking excellent candidates for about 10 postdoctoral positions in all areas of the Foundations of Computer Science.

lundi 22 octobre 2018, 11h10, Salle 1007
Marie Fortin (LSV - ENS Paris-Saclay) It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with “Happened Before”

Message sequence charts (MSCs) naturally arise as executions of communicating finite-state machines (CFMs), in which finite-state processes exchange messages through unbounded FIFO channels. We study the first-order logic of MSCs, featuring Lamport's happened-before relation. We introduce a star-free version of propositional dynamic logic (PDL) with loop and converse. Our main results state that (i) every first-order sentence can be transformed into an equivalent star-free PDL sentence (and conversely), and (ii) every star-free PDL sentence can be translated into an equivalent CFM. This answers an open question and settles the exact relation between CFMs and fragments of monadic second-order logic. As a byproduct, we show that first-order logic over MSCs has the three-variable property.

This is joint work with Benedikt Bollig and Paul Gastin, presented at CONCUR’18.

Combinatoire énumérative et analytique
jeudi 25 octobre 2018, 11h45, Salle 1007
Erik Slivken (Université Paris 7, LPSM) Large random pattern-avoiding permutations

A pattern in a permutation is a subsequence with a specific relative order. What can we say about a typical large random permutation that avoids a particular pattern? We use a variety of approaches. For certain classes we give a geometric description that relates these classes to other types of well-studied concepts like random walks or random trees. Using the right geometric description we can find the the distribution of certain statistics like the number and location of fixed points.

Preuves, programmes et systèmes
jeudi 25 octobre 2018, 10h30, Salle 3052
Carlo Spaccasassi (Microsoft Research Cambridge, Cambridge (United Kingdom)) Type-Based Analysis for Session Inference

We propose a type-based analysis to infer the session protocols of channels in an ML-like concurrent functional language. Combining and extending well-known techniques, we develop a type-checking system that separates the underlying ML type system from the typing of sessions. Without using linearity, our system guarantees communication safety and partial lock freedom. It also supports provably complete session inference with no programmer annotations. We exhibit the usefulness of our system with interesting examples, including one which is not typable in substructural type systems.

Gâteau du jeudi - Thursday Cake
jeudi 25 octobre 2018, 17h30, in front of room 3052
Ranadeep Biswas, Yves Guiraud, Alexandre Nolin, Exequiel Rivas (IRIF CakeTM) Gâteau de l'IRIF

IRIF CakeTM is an amazing opportunity to meet people while simultaneously eating cakes baked by your fellow colleagues! Join us every Thursday, at 5pm, in front of room 3052 (Sophie Germain 3rd floor) for a weekly feast. You can also express your cooking skills and volunteer to bake a cake by sending an email to cake@irif.fr.