Launching LMF - the Formal Methods Laboratory

The Laboratoire Méthodes Formelles (LMF) was founded on 1 January 2021 as a joint research centre of University Paris-Saclay, CNRS, ENS Paris-Saclay, Inria, and CentraleSupélec with a main focus on formal methods. The new laboratory combines the expertise of about 100 members from the former Laboratoire Spécification et Vérification (LSV) and the VALS team of Laboratoire de Recherche en Informatique (LRI).

In our mission to enlighten the digital world through Mathematical Logic, we rely on formal methods as a tool to analyse, model, and reason about computing systems, such as computer programs, security protocols, and hardware designs. Our research targets a wide range of computational paradigms, from classical to emerging ones such as biological and quantum computing.

LMF is structured around three hubs: Proofs and Models, which lie at the heart of our historical background, and Interactions, that is aimed at fostering cross-fertilisation between formal methods and other domains in computing science and beyond.

Science ouverte : Prix pour Coq

L'assistant de preuves Coq est d'abord un langage informatique qui permet d'écrire des définitions et des énoncés mathématiques, de décrire des structures de données informatiques et des algorithmes. Il s’agit aussi d’un environnement pour développer des preuves de théorèmes complètement vérifiées par l'ordinateur, par exemple, la correction d'un algorithme. Read more...

ACM Software System Award for Jacques-Henri Jourdan / CompCert

Association for Computing Machinery (ACM) logo

Jacques-Henri Jourdan receives the 2021 ACM Software System Award together with Xavier Leroy, Sandrine Blazy, Zaynah Dargaye, Michael Schmidt, Bernhard Schommer, and Jean-Baptiste Tristan for their work on the CompCert formally verified compiler.

CompCert, initiated in 2005, is a compiler for the C programming language and the first industrial-strength compiler with a formally verified proof of correctness. It generates optimized code for most common computer architectures including PowerPC, ARM, RISC-V and x86.

The ACM Software System Award honours people or organizations "recognized for developing a software system that has had a lasting influence, reflected in contributions to concepts, in commercial acceptance, or both". The 2021 award is endowed with a prize of $35,000 sponsored by IBM.

Algorithm for consistent query answering under primary key constraints

Speaker: Anantha Padmanabha, ENS Ulm.

Tuesday May 10 2022, 11:00, (salle 1Z76 ENS Paris-Saclay and online)

Abstract: Databases often have constraints. However, these days it is common to have databases that violate such constraints. Such a database is called an “inconsistent database”. One of the basic constraints is the “primary key constraint” which states there can be at most one tuple for every primary key. If a database violates primary key constraint, it will contain more than one tuple for the same primary key. In this setting, the notion of a repair is defined by picking exactly one tuple for each primary key (maximal consistent subset of the database). A Boolean conjunctive query q, is certain for an inconsistent database D if q evaluates to true over all repairs of D. In this context, we have a dichotomy conjecture that states that for a fixed boolean conjunctive query q, testing whether q is certain for an input database D is either polynomial time or coNP-complete.

The conjecture is open in general, but has been verified for self-join-free and path queries. However, the polynomial time algorithms known in the literature are complex and use different strategies in the two cases. We propose a simple inflationary fixpoint algorithm for consistent query answering which correctly computes certain answers when the query q falls in the polynomial time cases for self-join-free queries and path queries. This raises a natural question, whether this algorithm works for all polynomial time cases. We answer this negatively and show that there are polynomial time certain queries (with self-joins) which cannot be computed by such an algorithm.

This is a joint ongoing work with Diego Figueira, Luc Segoufin and Cristina Sirangelo.

Hubert Comon Retirement Workshop

Hubert Comon has just retired. A celebration workshop in his honour will take place at ENS Paris-Saclay in the "Grand Amphithéâtre" on June 16, 2022. The event is joint with the final meeting of the ANR TECAP project.

Hubert Comon