### Institut de Recherche en Informatique Fondamentale

 L'IRIF est une unité mixe de recherche (UMR 8243) du CNRS et de l'Université Paris-Diderot, issue de la fusion des deux UMR LIAFA et PPS au 1er janvier 2016. Ses objectifs scientifiques se déclinent selon trois grandes thématiques au cœur de l'informatique : les fondements mathématiques de l’informatique ; les modèles de calcul et de preuves ; la modélisation, les algorithmes et la conception de systèmes. Voir plus ici.

#### Prochains séminaires

Vendredi 21 octobre 2016 · 14h30 · Salle 1006

Automates · Georg Zetzsche (LSV, ENS de Cachan) · Subword Based Abstractions of Formal Languages

A successful idea in the area of verification is to consider finite-state abstractions of infinite-state systems. A prominent example is the fact that many language classes satisfy a Parikh's theorem, i.e. for each language, there exists a finite automaton that accepts the same language up to the order of letters. Hence, provided that the abstraction preserves pertinent properties, this allows us to work with finite-state systems, which are much easier to handle.

While Parikh-style abstractions have been studied very intensely over the last decades, recent years have seen an increasing interest in abstractions based on the subword ordering. Examples include the set of (non necessarily contiguous) subwords of members of a language (the downward closure), or their superwords (the upward closure). Whereas it is well-known that these closures are regular for any language, it is often not obvious how to compute them. Another type of subword based abstractions are piecewise testable separators. Here, a separators acts as an abstraction of a pair of languages.

This talk will present approaches to computing closures, deciding separability by piecewise testable languages, and a (perhaps surprising) connection between these problems. If time permits, complexity issues will be discussed as well.

Lundi 24 octobre 2016 · 11h00 · Salle 1007

Vérification · Sylvain Schmitz (LSV - ENS Cachan) · Ideal Decompositions for Vector Addition Systems

Vector addition systems, or equivalently Petri nets, are one of the
most popular formal models for the representation and the analysis
of parallel processes. Many problems for vector addition systems are
known to be decidable thanks to the theory of well-structured
transition systems. Indeed, vector addition systems with
configurations equipped with the classical point-wise ordering are
well-structured transition systems. Based on this observation,
problems like coverability or termination can be proven
decidable. However, the theory of well-structured transition systems
does not explain the decidability of the reachability problem. In
this presentation, we show that runs of vector addition systems can
also be equipped with a well quasi-order. This observation provides
a unified understanding of the data structures involved in solving
many problems for vector addition systems, including the central
reachability problem. 
Joint work with Jérôme Leroux.</well>

</collapse>

Mardi 25 octobre 2016 · 11h00 · Salle 1007

Algorithmes et complexité · Eric Angel (Université d'Évry Val d'Essonne IBISC) · Clustering on k-edge-colored graphs.

We study the Max k-colored clustering problem, where, given an edge-colored graph with k colors, we seek to color the vertices of the graph so as to find a clustering of the vertices maximizing the number (or the weight) of matched edges, i.e. the edges having the same color as their extremities. We show that the cardinality problem is NP-hard even for edge-colored bipartite graphs with a chromatic degree equal to two and k ≥ 3. Our main result is a constant approximation algorithm for the weighted version of the Max k-colored clustering problem which is based on a rounding of a natural linear programming relaxation. For graphs with chromatic degree equal to two, we improve this ratio by exploiting the relation of our problem with the Max 2-and problem. We also present a reduction to the maximum-weight independent set (IS) problem in bipartite graphs which leads to a polynomial time algorithm for the case of two colors.

Mardi 25 octobre 2016 · 14h00 · Salle 1007

Algorithmique distribuée et graphes · Jonas Lefevre (IRIF) · Self-stabilizing Metric Graphs

Je présenterai un algorithme autostabilisant pour réseaux overlay construisant le graphe d'une métrique donnée par oracle. L'algorithme fonctionne sous les daemons synchrones et asynchrones. Sous daemon synchrone le temps de convergence est linéaire. Dans tout les cas, la complexité en messages et celle en mémoire sont aussi faibles que possible. Cette construction peut être utilisée pour construire pour de la construction d'un graphe arbitraire.

Vendredi 28 octobre 2016 · 10h30 · Salle 3052, Bâtiment Sophie Germain (SEE NOTE IN THE ABSTRACT)

Séminaire de l'IRIF · Yuri Gurevich (Microsoft Research) · IRIF expository talks series : Logic in Computer Science and Computer Engineering

In software industry, engineers do formal logic day in and day out, even though they may not realize that. As a rule, they have not studied logic. Instead, they spent a lot of time studying calculus which they use rarely, if ever. I'll try to illustrate why logic is so relevant and why it is hard for software engineers to pick it up.

IMPORTANT NOTE: For administrative reasons, those from outside of IRIF who wish to attend the seminar in “Salle 3052” should email by Wednesday 26/10 their name to Irène Guessarian at ig@liafa.univ-paris-diderot.fr .

Vendredi 28 octobre 2016 · 14h30 · Salle 1006

Automates · Vincent Jugé (LSV, ENS de Cachan) · TBA

#### Événements

Mardi 11 octobre 2016 · 14h · Salle 1006

Jury

Mme Frédérique Bassino, professeure, Université Paris-Nord, examinatrice
Mme Mireille Bousquet-Mélou, directrice de recherche CNRS, Université de Bordeaux, directrice
M. Guillaume Chapuy, chargé de recherche CNRS, Université Paris Diderot, directeur
M. Valentin Féray, assistant professor, Universität Zürich, examinateur
M. Emmanuel Guitter, ingénieur CEA et chercheur IPhT, examinateur
M. Christian Krattenthaler, professor, Universität Wien, rapporteur (absent)
M. Bruno Salvy, chercheur INRIA, ENS de Lyon, examinateur
M. Gilles Schaeffer, directeur de recherche CNRS, École polytechnique, rapporteur

Résumé

Le sujet de cette thèse est l'étude énumérative des cartes combinatoires et ses applications à l'énumération d’autres objets combinatoires.

Les cartes combinatoires sont un modèle combinatoire riche. Elles sont définies d’une manière intuitive et géométrique, mais elles sont aussi liées à des structures algébriques plus complexes. À la rencontre de différents domaines, les cartes peuvent être analysées par une grande variété de méthodes, et leur énumération peut aussi nous aider à compter d’autres objets combinatoires. Cette thèse présente un ensemble de résultats et de connexions très riches dans le domaine de l’énumération des cartes. Les résultats dans cette thèse se divise en deux grandes parties. La première partie contient mes travaux sur l'énumération des constellations, en utilisant les caractères du groupe symétrique ou bien en résolvant des équations fonctionnelles sur leur séries génératrices. La deuxième partie est sur le lien énumératif entre les cartes et d’autres objets combinatoires, par exemple les généralisations du treillis de Tamari et les graphes aléatoires qui peuvent être plongés dans une surface donnée.

Abstract

This thesis deals with the enumerative study of combinatorial maps, and its application to the enumeration of other combinatorial objects.

Combinatorial maps form a rich combinatorial model. They have an intuitive and geometric definition, but are also related to some deep algebraic structures. Standing on a position where many domains meet, maps can be studied using a large variety of methods, and their enumeration can also help us count other combinatorial objects. This thesis is a sampling from the rich results and connections in the enumeration of maps. Results in this thesis can be structured into two major parts. The first part contains my work in the enumeration of constellations, using characters of the symmetric group or by solving functional equations of their generating functions. The second part shows some enumerative links from maps to other combinatorial objects, such as generalizations of the Tamari lattice and random graphs embeddable onto surfaces.

Lundi 28 - Mardi 29 novembre 2016 · Amphi Turing / Salle des thèses

Dimanche 15 - Vendredi 20 Janvier 2017 · Jussieu