## Welcome

IRIF is a research laboratory of CNRS and Université Paris Cité, also hosting one Inria project-team.

The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences.

IRIF hosts about 200 people. Six of its members have been distinguished by the European Research Council (ERC), six are members of the Institut Universitaire de France IUF), two are members of the Academia Europæa, and one is member of Académie des sciences.

## Notion of the day

## News

*28.9.2022*

**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:

*19.9.2022*

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.

*7.9.2022*

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.

*11.8.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**.

*2.9.2022*

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**.

*2.9.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**.

*31.8.2022*

**Baptiste Louf**, a former IRIF PhD. student is the 2021 winner of the Chancellerie des Universités de Paris thesis award in the “all specialties” science category. Learn more about his work in this written interview.

*2.9.2022*

The 2nd Workshop Complexity and Algorithms (CoA 2022) will take place in **September 26-28 2022** at Institut Henri Poincaré (IHP), Paris.
Scientific program includes talks from invited speakers **Marthe Bonamy (LaBRI)**, **Carola Doerr (LIP6)**, **Sébastien Tavenas (LAMA)** and **Adrian Vladu (IRIF)**.

(These news are displayed using a randomized-priority ranking.)

## Agenda

One world numeration seminar

Tuesday October 4, 2022, 2PM, Online

**David Siukaev** (Higher School of Economics) *Exactness and Ergodicity of Certain Markovian Multidimensional Fraction Algorithms*

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

Tuesday October 4, 2022, 2:30PM, Online

**Alexandra Skripchenko** (Higher School of Economics) *Bruin-Troubetzkoy family of interval translation mappings: a new glance*

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.

Algorithms and complexity

Wednesday October 5, 2022, 4:30PM, Salle 3052

**Daniel Szilagyi & Brandon Augustino** *Seminar Paris-Lehigh on Quantum Interior Point Methods*

Enumerative and analytic combinatorics

Thursday October 6, 2022, 2PM, IHP

**Seminaire Flajolet** *Jehanne Dousse, Nicolas Bonichon, Thierry Levy*

Proofs, programs and systems

Thursday October 6, 2022, 10AM, Salle 3052

**All Hands On Deck** (IRIF) *Matinée de rentrée de PPS*

PhD students seminar

Thursday October 6, 2022, 4PM, 3052

**Adrienne Lancelot** *Equivalences of Programs in the lambda calculus*

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.

Higher categories, polygraphs and homotopy

Friday October 7, 2022, 2PM, Salle 1007

**Pierre-Louis Curien** (IRIF) *Une preuve élémentaire de ce que les ensembles opétopiques sont les polygraphes ``many-to-one’’*

Automata

Friday October 7, 2022, 2PM, Salle 3052

**Jacques Sakarovitch** (IRIF, CNRS and LTCI, Télécom Paris, IPP) *The Net Automaton of a Rational Expression*

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

Friday October 7, 2022, 3PM, online

**Arend Rensink** (Department of Computer Science, University of Twente, Netherlands) *GROOVE: A tutorial overview*

Verification

Monday October 10, 2022, 11AM, 1007 and Zoom link

**Cristina Seceleanu** (Mälardalen University) *Reinforcement Learning for Mission Plan Synthesis of Autonomous Vehicles*