Simon Vilmin (LIS, Univ. Marseille)

Un système de fermeture sur un univers (fini) X est une famille de sous-ensembles de X, dits fermés, close par intersection et contenant X. Ces systèmes apparaissent dans de nombreux champs de l’informatique et des mathématiques par le biais de représentations implicites. Parmi les représentations possibles, deux sont communes :

  • les bases d’implications, soit des ensembles de règles A –> b signifiant “un ensemble contenant l’ensemble A doit contenir l’élément b” ;
  • l’ensemble des fermés (inf-)irréductibles, ces derniers étant les fermés à partir duquel reconstruire tout le système.

Dans cet exposé, je donnerai d’abord une introduction générale aux systèmes de fermetures, leurs représentations. Puis, je présenterai les résultats d’une collaboration avec Kira Adaricheva et Lhouari Nourine concernant la D-base, une base d’implications particulière. Plus précisément, je décrirai des algorithmes permettant de trouver (i.e. énumérer) la D-base depuis des fermés irréductibles ou depuis une autre base d’implications.

English version

Computing the D-base of finite closure systems

A closure system over a (finite) set X is a collection of subsets of X, called closed sets, being closed under intersection and containing X. These systems appear in disguise in numerous fields of mathematics and computer science by means of implicit representations. There are two common representations of a closure system:

  • implicational bases (IBs), that is sets of rules A –> b meaning “a set containing the set A must contain the element b”;
  • the family of (meet-)irreducible closed sets, being the closed sets from which one can rebuild the whole closure system.

In this talk, I will first give a general overview of closure systems and their representations. Then, I will present the results of a collaboration with Kira Adaricheva and Lhouari Nourine regarding the D-base, particular IB. More precisely, I will describe algorithms to retrieve (i.e. enumerate) the D-base either from irreducible closed sets or from an arbitrary IB.