The joy of implications, aka pure Horn functions: mainly a survey <s> Shock <s> Closure systems C ⊂ 2Mon a finite set M arise in many areas of discrete mathematics. They are conveniently encoded by either the family Irr(C) of meet irreducible closed sets, or by implicational bases Σ. We significantly improve six (partly little known) algorithms in order to settle the problems (a),(b),... (g) listed below. In particular, the algorithm LINCLOSURE, which is well known in relational database theory, is enhanced. It appears as a subroutine in three of our algorithms. Applications in database theory, matroid theory and algebra will be pointed out. <s> BIB001 </s> The joy of implications, aka pure Horn functions: mainly a survey <s> Shock <s> Recently concept lattices became widely used tools for intelligent data analysis. In this paper, several algorithms that generate the set of all formal concepts and diagram graphs of concept lattices are considered. Some modifications of wellknown algorithms are proposed. Algorithmic complexity of the algorithms is studied both theoretically (in the worst case) and experimentally. Conditions of preferable use of some algorithms are given in terms of density/sparseness of underlying formal contexts. Principles of comparing practical performance of algorithms are discussed. <s> BIB002 </s> The joy of implications, aka pure Horn functions: mainly a survey <s> Shock <s> Implications of a formal context obey Armstrong rules, which allows one to define a minimal (in the number of implications) implication basis, called Duquenne-Guigues basis or stem base in the literature. In this paper we show how implications are reduced to functional dependencies and prove that the problem of determining the size of the stem base is a #P-complete problem. <s> BIB003
Proof. We draw on [MR2, Lemma 13.3 and Cor.13.1]. We first show that for any fixed e ∈ E it holds for all Y ⊆ E that: Proof of (24). Suppose Y is such that e ∈ c(Y ) = ∩{X ∈ M (F) : X ⊇ Y }; see (4). Thus from X ∈ M (F) and X ⊇ Y follows e ∈ X. For each X ∈ max(F, e) ⊆ M (F) (see (21)) we have e ∈ X, hence X ⊇ Y , hence Y ∩ (E\X) = ∅, hence Y ∈ T r(cmax (F, e) ). Conversely, let Y be such that e ∈ c(Y ). Then, because of c( with e ∈ X ⊇ Y . We may assume that X is maximal within M (F) with respect to e ∈ X. It then follows from (22) (put H := M (F)) that X ∈ max (F, e) . From X ⊇ Y it follows that Y ∩ (E\X) = ∅, and so Y ∈ T r(cmax (F, e) ). This proves (24). Let e ∈ E be fixed. Then the family of minimal Y 's satisfying e ∈ c(Y ) is stems(r) ∪ {e}. Likewise the family of minimal Y 's satisfying Y ∈ T r(cmax (F, e) ) is mtr(cmax (F, e) ). By (24) these two set families coincide, which proves (a). As to (b), it follows from (a) and (20) that mtr(stems(e) ∪ {e}) = mtr(mtr(cmax(F, e))) = cmax(F, e). As was independently done in [BDVG] , let us discuss the six directions in the triangle of Figure 7 . Notice that matters don't change much if instead of M (F) we substitute any "small" (informal notion) generating set H of F in Figure 7 , and instead of Σ GD we sometimes consider any "small" (w.r.t. Σ GD ) base Σ of F. Both practical algorithms illustrated by examples, and theoretic complexity will be discussed. As to going from Σ cd to a minimum base Σ, the most elegant and only slightly sub-optimal method is the one of Shock [Sh] ; see Expansion 11. The way from Σ to Σ cd can be handled by the consensus method (Expansion 7); for another method see [RCEM] . In Subsections 3.6.1 to 3.6.3 we outline how to travel the remaining four directions, with more details provided in Expansions. 3.6.1 Recall from Theorem 2 that knowing the canonical direct base Σ cd means knowing the members of {stems(e) : e ∈ E}. Likewise, by (21) and (23), knowing M (F) amounts to knowing the set collections cmax(F, e) (e ∈ E). Therefore Theorem 4 says that getting Σ cd from M (F) or vice versa is as difficult as calculating all minimal transversals of a hypergraph. To fix ideas let us carry out the way from M (F) to Σ cd on a toy example. Suppose that E = [6] and F is such that 12345, 124, 1245, 13456, 245, 25, 3456, 356}. From (21) and (22) we get The set union in (26) happens to be disjoint. Generally the union in (21) is disjoint iff |X * \X| = 1 for all X ∈ M (F). Here X * is the unique upper cover of X in F. From say max(F, 4) = {25, 12, 356} we get cmax(F, 4) = {1346, 3456, 124}, and by Theorem 4(a) we have stems(4) ∪ {4} = mtr({1346, 3456, 124}) which turns out to be {4, 13, 16, 23, 26, 15}. Dropping {4} yields stems(4). Likewise one calculates stems(1) = {23, 26}, stems(3) = {6}, stems(5) = {3, 6}, stems(2) = stems(6) = ∅. By definition of Σ cd in Theorem 2 we conclude that (27) Σ cd = {13 → 4, 16 → 4, 23 → 14, 26 → 14, 15 → 4, 6 → 35, 3 → 5}. Let us mention a natural enough alternative [W1, Algorithm 3] for M (F) → Σ cd . By processing the members of M (F) one-by-one it updates a corresponding direct base. The worst case complexity being poor, average behaviour still awaits proper evaluation. 3.6.2 How to get M (F) from an arbitrary (non-direct) implication base Σ? One of the first methods was [MR2, Algorithm 13.2], which was improved in BIB001 Sec.9] . In brief, in view of (21) both methods proceed as follows. Then max(i, e) := max(F(Σ i ), e) can be expressed in terms of the set families max(i − 1, e) and max(i − 1, a) where a ranges over A i . Another idea for Σ → M (F) in [BMN] features an interesting fixed-parameter-tractability result. Expansion 8 exhibits a fourth way. 3.6.2.1 Unfortunately it is shown in [KKS] that |M (F)| can be exponential with respect to |Σ|, and vice versa. Furthermore, according to [K] both transitions Σ → M (F) and M (F) → Σ are at least as hard as the transversal hypergraph problem. What's more, whatever the complexity of these transitions, they are equivalent under polynomial reductions. Along the way a fifth algorithm [K, p.360-361] to get the characteristic models (i.e. M (F)) from Σ is offered. (Some of these results extend to the arbitrary Horn functions in 4.5.) Open Problem 1: Compare on a common platform and in a careful manner akin to BIB002 , mentioned five methods (and possibly others) for calculating M (F) from Σ. 3.6.3 How can one conversely get a small or minimum base Σ from M (F) (or from another generating set H ⊆ F)? This process is nowadays known as Strong Association Rule Mining (applications follow in 3.6.3.4). For succinctness, suppose we want Σ = Σ GD . Unfortunately, as shown in BIB003 , not only can |Σ GD | be exponential in the input size |M (F)| × |E|, but also calculating the number |Σ GD | is #P -hard. Despite the exponentiality of |Σ GD | one could imagine (in view of (36)) that Σ GD can at least be generated in output-polynomial time, given M (F). As shown in [DS] , this problem is at least as hard as generating all minimal transversals. Given M (F), the pseudoclosed sets cannot be enumerated in lexicographic order [DS] , or reverse lexicographic order [BK] , with polynomial delay unless N P = P . Several related results are shown in [BK] . For instance, given H ⊆ P(E) and A ⊆ E, it is coN P -complete to decide whether any minimum base Σ of F(H) (see 2.1.1) contains an implication of type A → B. (Conversely, F can also be "large" with respect to Σ GD , see Expansion 4.) 3.6.3.1 A different approach to go from H to a small base Σ of F = F(H) was hinted at in [W1, p.118 ] and developed in [RDB] . It essentially amounts to a detour H → M (F) and then M (F) → Σ cd → Σ, but in a clever way that avoids to generate large chunks of Σ cd . It is argued that even if the resulting base Σ is considerably larger than Σ GD , this is more than offset by the short time to obtain Σ. A similar approach is taken in  , but instead of Σ cd the D-basis of 4.3 (a subset of Σ cd ) is targeted. Furthermore the likely superior [MU] subroutine for hypergraph dualization is used. 3.6.3.2 In another vein, it was recently observed in [R] that for given H ⊆ P(E) one can readily exhibit a set Σ of implications based on a superset E ⊇ E such that F := F(Σ ) satisfies F [E] = F(H). Here F [E] := {X ∩ E : X ∈ F } is the projection of F upon E. Furthermore, |E | = |E| + |H| and Σ has a mere 2|E| implications. What also is appealing: If F is given by 012n-rows as in 4.4 then F [E] is smoothly calculated by setting to 0 all components with indices from E \ E, and adapting the other components accordingly.