On the Usability of Probably Approximately Correct Implication Bases

From a practical point of view, computing implication bases of formal contexts is a challenging task. The reason for this is twofold: on the one hand, bases of formal contexts can be of exponential size [14] (see also an earlier work [12] for the same result presented in different terms), and thus just writing out the result can take a long time. On the other hand, even in cases where implication bases can be small, efficient methods to compute them are unknown in general, and running times may thus be much higher than necessary. This is particularly true for computing the canonical basis, where only very few algorithms [9, 15] are known, which all in addition to the canonical basis have to compute the complete concept lattice. The authors of this work are given in alphabetical order. No priority in authorship is implied. 2 Daniel Borchmann, Tom Hanika, and Sergei Obiedkov Approaches to tackle this problem are to parallelize existing algorithms [13], or restrict attention to implication bases that are more amenable to algorithmic treatment, such as proper premises [16] or D-bases [1].