Séminaire Algorithmique : « A propos du calcul de la D-base des systèmes de fermeture finis », Simon Vilmin (LIS, Univ. Marseille)

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.