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.

9.1.2019
IRIF has the great pleasure to welcome Jeremy Siek, professor at Indiana University Bloomingtom, who is visiting IRIF for five months. Jeremy is the creator of gradual typing and a world-renowed expert in typed programming languages. Meet him in office 4034a.

Gradual typing is a technique that allows the programmer to control which parts of a program check their type correctness (i.e., that apples are added to apples) before execution and which parts check it during their execution instead. It is often used to gradually add the before-execution check to dynamic languages, like JavaScript, which perform the check only at run-time, since it is generally better to find errors before the execution of a program rather than during its execution.

10.1.2019
The day of the ASV pole will take place Monday January 21.

29.11.2018
Constantin Enea from IRIF organizes with Ruzica Piskac (Yale University), the 20th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2019). The conference is preceded by a winter school on formal methods.

16.1.2019
Giuseppe Castagna, Victor Lanvin, Tommaso Petrucciani from IRIF present this week at POPL19 a paper coauthored with Jeremy Siek (Indiana university) about a new formal framework for gradual typing allowing a smoother and more declarative integration of gradual typing in existing programming languages.

17.1.2019
Guillaume Chapuy and Enrica Duchi from IRIF coorganize with Christina Goldschmidt (Oxford) the Journées Aléa 2019, a CNRS thematic school about discrete random structures, from 03-18 to 03-22 at CIRM. Register by January 23.

8.1.2019
IRIF has the great pleasure to welcome a new researcher (CNRS), Amaury Pouly, an expert in continuous models of computations, and the analysis and verification of continuous/hybrid dynamical systems.

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

19.12.2018
Fabian Reiter now at LSV was awarded the Honorable Mention of the Gilles Kahn prize for his PhD Distributed Automata and Logic supervised by Olivier Carton at IRIF.

Combinatoire énumérative et analytique
Jeudi 17 janvier 2019, 11 heures 45, Salle 1007
Philippe Nadeau (Institut Camille Jordan (Lyon)) La symétrisation divisée

La symétrisation divisée est un opérateur linéaire sur les polynômes multivariés. Il a été introduit pour exprimer le volume des permutoèdres généralisés, et apparaît également dans le contexte du calcul de Schubert pour la variété de drapeaux. Nous expliquerons ces termes et décrirons divers aspects combinatoires et algébriques de la symétrisation divisée, notamment son action sur diverses familles de polynômes. Travail en commun avec V. Tewari (UPenn)

Prochaine séance
Jeudi 17 janvier 2019, 17 heures 30, in front of room 3052
Cédric Ho Thanh, Farzad Jafarrahmani, Nicolas Jeannerod (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 [email protected]

Catégories supérieures, polygraphes et homotopie
Vendredi 18 janvier 2019, 14 heures, Salle 1007
Benjamin Dupont (Université de Lyon) Cohérence modulo et doubles groupoïdes

Catégories supérieures, polygraphes et homotopie
Vendredi 18 janvier 2019, 10 heures, 3052
Amar Hadzihasanovic (RIMS Kyoto University) Charted omega-categories

A charted omega-category is like a strict omega-category, but instead of a globular set, it has an underlying regular polygraph: its cells have more complex pasting diagrams “charted” on their boundary. Several features of omega-categories generalise nicely, including joins and the monoidal biclosed structure of lax Gray products. I will detail some of the combinatorics involved, going deeper into the theory of globular posets than in my talk last July (which is not a prerequisite).

Automates
Vendredi 18 janvier 2019, 14 heures 30, Salle 3052

We consider the problem of passive symbolic learning in the case of deterministic top-down tree transducers (DTOP). The passive learning problem deals with identifying a specific transducer in normal form from a finite set of behaviour examples. This problem is solved in word languages using the RPNI algorithm, that relies heavily on the Myhill-Nerode characterization of a minimal normal form on DFA. Its extensions to word transformations and tree languages follow the same pattern: first, a Myhill-Nerode theorem is identified, then the normal form it induces can be learnt from examples. To adapt this result in tree transducers, the Myhill-Nerode theorem requires that DTOP are considered with an inspection, i.e. an automaton that recognized the domain of the transformation. In its original form, the normalization (minimal earliest compatible normal form) and learning of DTOP is limited to deterministic top-down tree automata as inspections. In this talk, we show the challenges that an extension to regular inspections presents, and present two concurrent ways to deal with them:
1. first, by an extension of the Myhill-Nerode theorem on DTOP to the regular case, by defining a minimal *leftmost* earliest compatible normal form.
2. second, by reducing the problem to top-down domains, by using the regular inspection as a lookahead

The merits of these methods will be discussed for possible extensions of these methods to data trees.

Systèmes complexes
Mardi 22 janvier 2019, 14 heures, Salle 3052
Guillaume Ducoffe (ICI Roumanie) Computing Giant Diameters with Breadth-First Search and Range Queries

A well-known problem for which it is difficult to improve the textbook algorithm is computing the graph diameter. We present two versions of a simple algorithm (one being Monte Carlo and the other deterministic) that for every fixed $h$ and unweighted undirected graph $G$ with $n$ vertices and $m$ edges, either correctly concludes that $diam(G) < hn$ or outputs $diam(G)$, in time ${\cal O}(m+n^{1+o(1)})$. The algorithm combines a simple randomized strategy for this problem (Damaschke, {\it IWOCA'16}) with a popular framework for computing graph distances that is based on range trees (Cabello and Knauer, {\it Computational Geometry'09}). We also prove that under the Strong Exponential Time Hypothesis (SETH), we cannot compute the diameter of a given $n$-vertex graph in truly subquadratic time, even if the diameter is an $\Theta(n/\log{n})$.

Graphes
Mardi 22 janvier 2019, 14 heures, Salle 3052
Guillaume Ducoffe (ICI Roumanie) Computing Giant Diameters with Breadth-First Search and Range Queries

A well-known problem for which it is difficult to improve the textbook algorithm is computing the graph diameter. We present two versions of a simple algorithm (one being Monte Carlo and the other deterministic) that for every fixed $h$ and unweighted undirected graph $G$ with $n$ vertices and $m$ edges, either correctly concludes that $diam(G) < hn$ or outputs $diam(G)$, in time ${\cal O}(m+n^{1+o(1)})$. The algorithm combines a simple randomized strategy for this problem (Damaschke, {\it IWOCA'16}) with a popular framework for computing graph distances that is based on range trees (Cabello and Knauer, {\it Computational Geometry'09}). We also prove that under the Strong Exponential Time Hypothesis (SETH), we cannot compute the diameter of a given $n$-vertex graph in truly subquadratic time, even if the diameter is an $\Theta(n/\log{n})$.

Preuves, programmes et systèmes
Jeudi 24 janvier 2019, 10 heures 30, Ens Lyon
Seminaire Chocola (Ens Lyon) Non encore annoncé.