A fast algorithm for building lattices

This paper presents a simple, efficient algorithm to compute the covering g raph of the lattice generated by a family B of subsets of a set X. The impl ementation of this algorithm has O((\X\ + \B\).\B\) time complexity per lat tice element. This improves previous algorithms of Bordat (1986), Ganter an d Kuznetsov (1998) and Jard et al. (1994). This algorithm can be used to co mpute the Galois (concept) lattice, the maximal antichains lattice or the D edekind-MacNeille completion of a partial order, without increasing time co mplexity. (C) 1999 Elsevier Science B.V. All rights reserved.