Institut de Recherche en Informatique Fondamentale

Research Institute for Foundations of Computer Science

IRIF Université Paris 7 CNRS IRIF is a research laboratory co-founded by the CNRS and the University Paris-Diderot, resulting from the merging of the two research units LIAFA and PPS on January 1st, 2016.

The scientific objectives of the laboratory are at the core of computer science, focusing on: the mathematical foundations of computer science; computational models and proofs; models, algorithms and system design.

Upcoming seminars

Jeudi 30 mars 2017 · 10h00 · Salle 3052

Preuves, programmes et systèmes · Giovanni Bernardi (IRIF) · Un, personne et cent mille: a meta theory for testing equivalences?

Testing theory focuses on contextual equivalences that were proposed in the 80s as an alternative to bisimulation equivalence. During the last decade testing equivalences proved useful in constructing semantic models of session types and in laying the foundations of web-service technologies. As result, testing theory is more useful and richer than ever. In this seminar I will recall the chief ideas behind testing theory, and argue that we lack a general methodology to reason on testing equivalences. I will also outline the evidence that a meta-theory may exist, and some open questions.

Jeudi 30 mars 2017 · 11h15 · Salle 3052

Preuves, programmes et systèmes · Daniela Petrisan (IRIF) · Hybrid set-vector automata from a category-theoretic perspective

The main purpose of this talk is to introduce a new automata model, hybrid set-vector automata, that naturally embed deterministic finite state automata and finite automata weighted over a field.

We take a category-theoretic approach, which provides a neat understanding of minimisation. It is well known that category theory offers a unifying view of some automata theory results. For example, minimisation of deterministic automata (over finite words) and Shützenberger’s automata weighted over fields, arise from the same categorical reasons.

In the first part of the talk, I will discuss about how to model and minimise automata in categories. Traditionally, automata are seen either as algebras for a functor plus a final map, possibly in a monoidal category, or as coalgebras for a functor plus an initial map. We propose yet another view of automata as functors from an input category to an output category.

The new hybrid set-vector automata can be modelled by taking the output category to be a free-colimit completion of the category of finite-dimensional vector spaces under a certain class of colimits.

This is joint work with Thomas Colocombet.

Vendredi 31 mars 2017 · 14h30 · Salle 1006

Automates · Cyril Nicaud (LIGM) · Synchronisation d'automates aléatoires

Il y a 50 ans, Cerny a posé une conjecture combinatoire sur les automates, qui n'est toujours pas résolue. Un automate est dit synchronisé quand il existe un mot u et un état p tel que depuis n'importe quel état, si on lit u on arrive en p. Sa conjecture est que si l'automate synchronisé possède n états, alors il existe un tel u de longueur au plus (n-1)2. Dans cet exposé, nous nous intéresserons à la version probabiliste de la conjecture de Cerny : on montrera qu'un automate aléatoire est non seulement synchronisé (résultat déjà prouvé par Berlinkov), mais qu'en plus la conjecture de Cerny est vraie avec forte probabilité.

Mardi 04 avril 2017 · 14h00 · Salle 1007

Algorithmique distribuée et graphes · Valentin Garnero (INRIA Sophia Antipolis) · TBA

Mercredi 05 avril 2017 · 11h00 · Salle 3052

Séminaire des doctorants · Guillaume Lagarde (Automata and applications Group) · TBA