Lattices, closures systems and implication bases: A survey of structural aspects and algorithms

Concept lattices and closed set lattices are graphs with the lattice property. They have been increasingly used this last decade in various domains of computer science, such as data mining, knowledge representation, databases or information retrieval. A fundamental result of lattice theory establishes that any lattice is the concept lattice of its binary table. A consequence is the existence of a bijective link between lattices, contexts (via the table) and a set of implicational rules (via the canonical (direct) basis). The possible transformations between these objects give rise to relevant tools for data analysis. In this paper, we present a survey of lattice theory, from the algebraic definition of a lattice, to that of a concept lattice, through closure systems and implicational rules; including the exploration of fundamental bijective links between lattices, reduced contexts and bases of implicational rules; and concluding with the presentation of the main generation algorithms of these objects.