Algorithms for Computing Concept Lattices: Theoretical Complexity Bounds and Experimental Results
by
Sergei O. Kuznetsov
TU-Dresden, Institut für Algebra, Dresden / VINITI, Moscow
Coauthors: Sergei A. Obiedkov (Russian State University for Humanities, Moscow)

By the main theorem of the Formal Concept Analysis, every finite lattice is isomorphic to a concept lattice. Therefore, the problem of computing a concept lattice is equivalent to computing a general lattice from the set of its meet and join irreducibles. The size of the lattice may be exponential w.r.t. the number of irreducibles and the problem of determining the size of a lattice, given its irreducibles, is #P-complete. We give a review of several algorithms computing concept lattices, discuss their theoretical worst-case complexity and results of computer experiments.

Date received: March 8, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caee-10.