Average Size of Implicational Bases
This addresses a computational bottleneck for researchers and practitioners in formal concept analysis by providing average-case efficiency guarantees, though it is incremental as it builds on existing methods.
The paper tackled the problem of the exponential worst-case size of implicational bases in formal concept analysis by showing that the base of proper premises has, on average, quasi-polynomial size, using results from random hypergraphs.
Implicational bases are objects of interest in formal concept analysis and its applications. Unfortunately, even the smallest base, the Duquenne-Guigues base, has an exponential size in the worst case. In this paper, we use results on the average number of minimal transversals in random hypergraphs to show that the base of proper premises is, on average, of quasi-polynomial size.