On the Complexity of Computing Generators of Closed Sets

Abstract. We investigate the computational complexity of some deci-sion and counting problems related to generators of closed sets funda-mental in Formal Concept Analysis. We recall results from the litera-ture about the problem of checking the existence of a generator with a specified cardinality, and about the problem of determining the number of minimal generators. Moreover, we show that the problem of counting minimum cardinality generators is #·coNP-complete. We also present an incremental-polynomial time algorithm from relational database theory that can be used for computing all minimal generators of an implication-closed set.