Institut de Recherche en Informatique Fondamentale (IRIF)


Université Paris Cité

L'IRIF est une unité mixte de recherche (UMR 8243) entre le CNRS et l'Université Paris Cité, qui héberge une équipe-projet 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), six sont membres de l'Institut Universitaire de France (IUF), deux sont membres de l'Academia Europæa, et un est membre de l'Académie des sciences.

Thomas Ehrhard

Thomas Ehrhard, CNRS senior researcher at IRIF, turned 60 in 2021. A meeting will take place in Paris, at the CNAM, on 29-30 September 2022 to celebrate Ehrhard’s contributions to logic and the semantics of programming languages. For more information, follow the arrow:

Test of Time Award - LICS'22

Philippe Schnoebelen (LMF), François Laroussinie (IRIF) and Nicolas Markey (IRISA), received the Test-of-Time award at the conference LICS 2022 for their research on temporal logic.

ICTP-EAUMP School on Mathematical Programming and Algorithms

IRIF is a co-sponsor of the ICTP-EAUMP School on Mathematical Programming and Algorithms - an African Mathematical School. The 2022 summer school organized by the University of Nairobi took place at Kenya School of Government, Nairobi, Kenya 11-29 July, 2022. Three IRIF members took part of this project: Jean-Baptiste Yunès, Roberto Mantaci and Anna Vanden Wyngaerd.

Prix de Thèse Gilles Kahn 2022

Le prix de thèse Gilles Kahn récompense chaque année une excellente thèse en informatique. Sont éligibles toutes les thèses soutenues au sein d’établissements français entre le 1er Septembre 2021 et le 31 Août 2022. Date limite de dépôt des candidatures : 16 septembre 2022.

ETAPS 2023

The next ETAPS conference, a forum of top-conferences in computer science, will happen in Paris, April 22-27 2023. Paper submission is opened until October 13, 2022, 23:59 AoE.

Podcast DECODE quantum

Pour son 48ème épisode, le podcast DECODE Quantum a reçu le directeur de l'IRIF Frédéric Magniez dans un entretien approfondi sur le quantique. Il est question, entre autres, d'algorithmes quantiques, de leur intérêt et de leur construction. Par ici pour écouter l'émission.

Prix Irène Joliot-Curie 2022

Plus que quelques jours pour déposer votre candidature au Prix Irène Joliot-Curie, ce prix qui vise à promouvoir la place des femmes dans la recherche et la technologie en France. Clôture des candidatures le 8/09/2022.

Accepted paper PODC 2022 R. Vacus & A. Korman

Amos Korman (IRIF) and Robin Vacus (IRIF) presented at PODC'22 their paper studying agreement processes in stochastic environments using minimal communication, inspired by biological scenarios.

(Ces actualités sont présentées selon un classement mêlant priorité et aléatoire.)

One world numeration seminar
Mardi 4 octobre 2022, 14 heures, Online
David Siukaev (Higher School of Economics) Exactness and Ergodicity of Certain Markovian Multidimensional Fraction Algorithms

A multidimensional continued fraction algorithm is a generalization of well-known continued fraction algorithms of small dimensions: Gauss and Euclidean. Ergodic properties of Markov MCF algorithms (ergodicity, nonsingularity, exactness, bi-measurability) affect their convergence (if the MСF algorithm is a Markov algorithm, there is a relationship between the spectral properties and its convergence).

In 2013 T. Miernowski and A. Nogueira proved that the Euclidean algorithm and the non-homogeneous Rauzy induction satisfy the intersection property and, as a consequence, are exact. At the end of the article it is stated that other non-homogeneous markovian algorithms (Selmer, Brun and Jacobi-Perron) also satisfy the intersection property and they also exact. However, there is no proof of this. In our paper this proof is obtained by using the structure of the proof of the exactness of the Euclidean algorithm with its generalization and refinement for multidimensional algorithms. We obtained technically complex proofs that differ from the proofs given in the article of T. Miernowski and A. Nogueira by the difficulties of generalization to the multidimensional case.

One world numeration seminar
Mardi 4 octobre 2022, 14 heures 30, Online
Alexandra Skripchenko (Higher School of Economics) Bruin-Troubetzkoy family of interval translation mappings: a new glance

In 2002 H. Bruin and S. Troubetzkoy described a special class of interval translation mappings on three intervals. They showed that in this class the typical ITM could be reduced to an interval exchange transformations. They also proved that generic ITM of their class that can not be reduced to IET is uniquely ergodic.

We suggest an alternative proof of the first statement and get a stronger version of the second one. It is a joint work in progress with Mauro Artigiani and Pascal Hubert.

Algorithmes et complexité
Mercredi 5 octobre 2022, 16 heures 30, Salle 3052
Daniel Szilagyi & Brandon Augustino Seminar Paris-Lehigh on Quantum Interior Point Methods

Combinatoire énumérative et analytique
Jeudi 6 octobre 2022, 14 heures, IHP
Seminaire Flajolet Jehanne Dousse, Nicolas Bonichon, Thierry Levy

Preuves, programmes et systèmes
Jeudi 6 octobre 2022, 10 heures, Salle 3052
All Hands On Deck (IRIF) Matinée de rentrée de PPS

Séminaire des doctorants
Jeudi 6 octobre 2022, 16 heures, 3052
Adrienne Lancelot Equivalences of Programs in the lambda calculus

In the study of programming languages, an essential point is the ability to state program equivalence, whether it is to reason abstractly or to establish that some program transformations, used typically when compiling programs, preserve the behavior of programs. The topic of this talk is the study of program equivalence for the case of programs expressed as terms of the λ-calculus, seen as a mathematical model of functional programming languages. We will survey existing program equivalences and focus on normal form bisimulations, in different variants of the lambda calculus. The lambda calculus was first introduced as a way to represent computable functions, with the Call-by-Name variant which has been extensively studied. Nowadays, functional programming languages use mostly the Call-by-Value variant (OCamL) and some the Call-by-Need variant (Haskell). In Call-by-Name, normal form bisimulations yield very satisfactory results. Unfortunately, these do not export to Call-by-Value. Part of my thesis work will be trying to find a satisfactory program equivalence in Call-by-Value.

The previous talk by Victor Arrial is a nice introduction to this talk but concepts tied to the lambda calculus (and its variants) will be re-explained. We will also need the (more generic) concept of co-induction to form program equivalences, which will be briefly explained as well.

Catégories supérieures, polygraphes et homotopie
Vendredi 7 octobre 2022, 14 heures, Salle 1007
Pierre-Louis Curien (IRIF) Une preuve élémentaire de ce que les ensembles opétopiques sont les polygraphes ``many-to-one’’

Vendredi 7 octobre 2022, 14 heures, Salle 3052
Jacques Sakarovitch (IRIF, CNRS and LTCI, Télécom Paris, IPP) The Net Automaton of a Rational Expression

In this talk, we present a new construction of a finite automaton associated with a rational (or regular) expression. It is very similar to the one of the so-called Thompson automaton, but it overcomes the failure of the extension of that construction to the case of weighted rational expressions. At the same time, it preserves all of the properties of the Thompson automaton.

This construction has two supplementary outcomes.

The first one is the reinterpretation in terms of automata of a data structure introduced by Champarnaud, Laugerotte, Ouardi, and Ziadi for the efficient computation of the position (or Glushkov) automaton of a rational expression, and which consists in a duplicated syntactic tree of the expression decorated with some additional links.

The second one supposes that this construction devised for the case of weighted expressions is brought back to the domain of Boolean expressions. It allows then to describe, in terms of automata, the construction of the Star Normal Form of an expression that was defined by Brüggemann-Klein, and also with the purpose of an efficient computation of the position automaton.

This is joint work with Sylvain Lombardy (Labri, U. Bordeaux)

Graph Transformation Theory and Applications
Vendredi 7 octobre 2022, 15 heures, online
Arend Rensink (Department of Computer Science, University of Twente, Netherlands) GROOVE: A tutorial overview

The graph transformation tool GROOVE is actively used in education and research, as an accessible and relatively powerful yet easy to use tool that incorporates many of the basic concepts and quite a number of more advanced GT-based features. However, being academy-ware, documentation is not its strongest point, and so some features are less visible and consequently under-used. In this presentation, I plan to demonstrate both the basic functionality (essentially, state space generation of a graph transformation system, with run-time isomorphism checking), as well as some of the more advanced features: - Typing, including subtyping, abstract types and type specialisation - Path expressions and label variables - Data manipulation, including algebra selection - Quantified rules, including the use of counting and multiary (i.e., set-based) operators - Rule control, including functions and (atomic) recipes.

Zoom meeting registration link

YouTube live stream

Lundi 10 octobre 2022, 11 heures, 1007 and Zoom link
Cristina Seceleanu (Mälardalen University) Reinforcement Learning for Mission Plan Synthesis of Autonomous Vehicles

Computing a mission plan for an autonomous vehicle consists of path planning and task scheduling, which are two outstanding problems existing in the design of multiple autonomous vehicles. Both problems can be solved by the use of exhaustive search techniques such as model checking and algorithmic game theory. However, model checking suffers from the infamous state-space-explosion problem that makes it inefficient at solving the problem when the number of vehicles is large, which is often the case in realistic scenarios. In this talk, we show how reinforcement learning can help model checking to overcome these limitations, such that mission plans can be synthesized for a larger number of vehicles if compared to what is feasibly handled by model checking alone. Instead of exhaustively exploring the state space, the reinforcement-learning-based method randomly samples the state space within a time frame and then uses these samples to train the vehicle models so that their behavior satisfies the requirements of tasks. Since every state of the model needs not be traversed, state-space explosion is avoided. Additionally, the method also guarantees the correctness of the synthesis results. The method is implemented in UPPAAL STRATEGO and integrated with a toolset to facilitate path planning and task scheduling in industrial use cases. We also discuss the strengths and weaknesses of using reinforcement learning for synthesizing strategies of autonomous vehicles.