betaFeedback

WorksComputer Science

A Polynomial Time Approximation for the Minimization of Implication Systems and Horn CNFs

Abstract

An implication system is a collection of rules of the form B \imp H, where the set BB of Boolean variables is the body of the rule, while HH is the set of its heads. Such a rule is an aggregate representation of individual implications B\imp h, for h∈Hh\in H which correspond to the clauses of an equivalent CNF representation of a Horn Boolean function. An implication system is body-minimum/clause-minimum if it has the minimum number of bodies/clauses among all logically equivalent implication systems. The corresponding minimization problems appear not only in the context of implication systems, but also as problems for closure systems, directed hypergraphs, representation of dependencies in relational databases, or in Horn CNF minimization. While body-minimization is known to be solvable in polynomial time (and there are several algorithms in the literature that solve this task), clause-minimization is known to be NP-hard. In fact, body-minimization has a particular canonical solution, called the GD-basis of the underlying Horn function that also can be computed efficiently. In this paper, we utilize a known connection between the two minimization problems stating that for every implication system there always exists a logically equivalent clause-minimum implication system which has the same bodies as its canonical GD-basis, see (B{é}rczi and B{é}rczi-Kov{á}cs, 2017), and (Adaricheva and Nation, 2014). We use this fact to design a polynomial time approximation algorithm which for any δ>0δ>0 outputs a (14+δ)n(\frac{1}{4} + δ)n-factor approximation of the logically equivalent clause-minimum implication system on nn variables. This is an improvement from the best known algorithm so far that provides only an (n−1)(n-1)-factor approximation, see (Hammer and Kogan, 1993).

Introduction

We consider a finite set VV of Boolean variables that can take only values true (denoted by 1) or false (denoted by 0). For a given subset B⊆VB \subseteq V and variable v∈Vv \in V, the implication B→vB \to v is the logical expression that evaluates to 0 if and only if all variables in BB have a value 1 and vv equals 0. We can read it as the statement “if all variables in BB are 1, then vv must also be 1” and we say that it is satisfied if it takes value 1. The set BB is called the body of the implication, while vv is its head. For subsets B,H⊆VB,H \subseteq V we denote by B→HB \to H the conjunction

⋀h∈H(B→h)\bigwedge_{h\in H}(B\to h)

and call it a rule. Note that B→vB \to v is always true if v∈Bv \in B, and hence we can assume w.l.o.g. that B∩H=∅B \cap H = \varnothing. To simplify our notation, we write B→hB \to h if H={h}H = \{h\}, and b→Hb \to H if B={b}B = \{b\}. An implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\}, where [m]={1,…,m}[m] = \{1,\ldots,m\}, is a collection of rules with Bi,Hi⊆VB_i,H_i \subseteq V for i∈[m]i \in[m], where the bodies BiB_i, i∈[m]i \in[m] are assumed to be pairwise distinct and each set of heads HiH_i, i∈[m]i \in[m] is assumed to be nonempty and disjoint from BiB_i (see e.g. [26] for more details about implication systems). A truth assignment x∈{0,1}Vx \in\{0,1\}^{V} is a satisfying assignment of Φ\Phi if it satisfies all implications of Φ\Phi. A Boolean function ff on variables from VV is a mapping f:{0,1}V→{0,1}f:\{0,1\}^{V} \to\{0,1\}. Clearly, every implication system Φ\Phi represents a Boolean function fΦf_{\Phi} on variables from VV where fΦ(x)=1f_{\Phi}(x)=1 if and only if x∈{0,1}Vx \in\{0,1\}^{V} is a satisfying assignment of Φ\Phi. Two implication systems Φ\Phi and Ψ\Psi are equivalent, denoted by Φ≡Ψ\Phi\equiv\Psi, if and only if fΦ=fΨf_{\Phi}=f_{\Psi}.

For instance, given four variables V={a,b,c,d}V=\{a,b,c,d\} we can consider the following set of implications: Φ={a→b, b→a, {a,c}→b, {a,c}→d}\Phi=\{a\to b,\ b\to a,\ \{a,c\}\to b,\ \{a,c\}\to d\}. This set can be written in a more concise equivalent form as an implication system

Φ′={a→b, b→a, {a,c}→{b,d}}.(1)\Phi'=\{a\to b,\ b\to a,\ \{a,c\}\to\{b,d\}\}. \tag*{(1)}

Setting variables aa and bb to 1, and cc and dd to 0 we get a satisfying assignment of Φ′\Phi', while setting aa, bb, and cc to 1 and dd to 0 is not satisfying.

Implication systems allow us to extend our knowledge about a partial satisfying assignment. For instance, assume that the variables of a subset S⊆VS \subseteq V are 1 in a satisfying assignment of the implication system Φ\Phi, given as above. If there exists an index 1≤i≤m1 \leq i \leq m such that Bi⊆SB_i \subseteq S and Hi⊈SH_i \not\subseteq S, then we can conclude that the variables in Hi∖SH_i \setminus S must also be 1, and hence we can extend SS to S∪HiS \cup H_i. Repeating this as many times as possible, we arrive to a subset S′⊇SS' \supseteq S such that for all indices i∈[m]i \in[m] we have either Bi⊈S′B_i \not\subseteq S' or Hi⊆S′H_i \subseteq S'. Such a subset S′S' is called a closed set with respect to Φ\Phi. The closure CΦ(S)C_{\Phi}(S) of an arbitrary subset S⊆VS \subseteq V is a minimal closed set with respect to Φ\Phi that contains SS. Note that the closure of a set can be efficiently derived by the above simple procedure, which we call forward chaining following the standard terminology. Furthermore, the closure of a set SS depends only on the underlying Boolean function, in other words, Φ≡Ψ\Phi\equiv\Psi if and only if CΦ(S)=CΨ(S)C_{\Phi}(S)=C_{\Psi}(S) for all S⊆VS \subseteq V (see e.g. [8, 20]). In the sequel we call CΦC_{\Phi} the closure operator of Φ\Phi. Furthermore, we denote by C(Φ)\mathcal{C}(\Phi) the family of closed sets with respect to the implication system Φ\Phi. Note again that Φ≡Ψ\Phi\equiv\Psi if and only if C(Φ)=C(Ψ)\mathcal{C}(\Phi)=\mathcal{C}(\Psi). Note also that closed sets are in a one-to-one correspondence with satisfying assignments. Namely, a subset S⊆VS \subseteq V is a closed set with respect to Φ\Phi if and only if assigning 1 to variables in SS and 0 to variables not in SS is a satisfying assignment of Φ\Phi.

By definition of the closure we have Bi∪Hi⊆CΦ(Bi)B_i \cup H_i \subseteq C_{\Phi}(B_i) for i∈[m]i \in[m], where some or even all of the containment relations may be strict. For instance, we can represent our small example above also as the equivalent implication system

Φ′′={a→b, b→a, {a,c}→d, {b,c}→d},\Phi^{\prime\prime} = \{a \to b,\ b \to a,\ \{a,c\} \to d,\ \{b,c\} \to d\},

where e.g., CΦ′({a,c})=CΦ′′({a,c})={a,b,c,d}C_{\Phi^\prime}(\{a,c\}) = C_{\Phi^{\prime\prime}}(\{a,c\}) = \{a,b,c,d\} so the containment is strict in Φ′′\Phi^{\prime\prime} for the body {a,c}\{a,c\}, while it is not strict in Φ′\Phi^\prime. Furthermore, we have {a,b}∈C(Φ′)\{a,b\} \in\mathcal{C}(\Phi^\prime), while {a,b,c}∉C(Φ′)\{a,b,c\} \notin\mathcal{C}(\Phi^\prime).

Let us recall that implication systems arise naturally in many different applications, and in many different contexts, resulting in different looking representations and terminology. Implication systems are used to describe the structure of relational databases [3, 8, 24], are equivalent to the family of definite Horn Boolean functions [18], and can equivalently be viewed as directed hypergraphs [6, 7]. They arise in formal concept analysis [19], in closure systems [26, 1], in machine learning [4, 5], in the theory of Boolean functions (Horn theory) [22, 25, 14, 17], etc. The family of Boolean functions that can be represented by implication systems is known as definite Horn functions (in some literature called pure Horn functions). The above cited forward chaining procedure that derives the closure of a set is known to run in polynomial time in the size of the input implication system (see e.g. [8, 20]).

Our small examples above (implication systems Φ′\Phi^\prime and Φ′′\Phi^{\prime\prime}) show that a Boolean function (a closure operator) may be represented by different logically equivalent implication systems. Since the computational time of various tasks, such as computing the closure of a set or answering a query in an expert system, depends on the implication system we use as an input, it is a frequently arising and important problem to find the shortest representation of a given implication system.

Since implication systems are used in the different contexts under different formalisms (e.g. directed hyperarcs, definite horn CNFs) there are numerous natural measures of “size” of an input and hence also numerous notions of “minimality”. Six different measures and the corresponding concepts of minimality were considered for an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} in [7, 17]:

  • (B) number of bodies: mm,

  • (BA) body area: ∑i=1m∣Bi∣\sum_{i=1}^{m} |B_i|,

  • (C) number of clauses: ∑i=1m∣Hi∣\sum_{i=1}^{m} |H_i|,

  • (TA) total area: ∑i=1m(∣Bi∣+∣Hi∣)\sum_{i=1}^{m} (|B_i| + |H_i|),

  • (BC) number of bodies and clauses: ∑i=1m(∣Hi∣+1)\sum_{i=1}^{m} (|H_i| + 1), and

  • (L) number of literals: ∑i=1m(∣Bi∣+1)⋅∣Hi∣\sum_{i=1}^{m} (|B_i| + 1) \cdot|H_i|.

With a slight abuse of notations we shall use (B), (BA), (TA), (C), (BC) and (L) to denote both the measures and the corresponding minimization problems.

The only one of these six minimization problems for which a polynomial time procedure exists to derive a minimum representation is (B). The first such algorithm appeared in database theory literature [24]. Different algorithms for the same task were then independently discovered in hypergraph theory [7], and in the theory of closure systems [19].

For the remaining five measures it is NP-hard to find the shortest representation. There is an extensive literature on the intractability results in various contexts for these minimization problems [24, 7, 20]. It was shown that (C) and (L) stay NP-hard even when the inputs are limited to bodies of size at most two [15], and the same result extends to the remaining three measures. Note that if all bodies are of size one then the above problems become equivalent with the transitive reduction of directed graphs, which is tractable [2]. It should be noted that there exist several other tractable subclasses, see [21, 13]. For the subclass of key-Horn implication systems, it was shown that (BA) becomes tractable while the remaining four problems stay NP-hard [23] but all admit a logarithmic factor approximation [10]. There are also few older heuristic minimization approaches for (C) and (L) [12].

It was shown that (C) and (L) are not only hard to solve exactly but even hard to approximate. More precisely, [11] shows that these problems are inapproximable within a factor log⁡1−ε(n)\log^{1-\varepsilon}(n) assuming NP⊈DTIME(npolylog⁡(n))NP \not\subseteq DTIME(n^{\operatorname{polylog}(n)}), where nn denotes the number of variables. In addition, [16] shows that they are inapproximable within a factor 2log⁡1−o(1)n2^{\log^{1-o(1)} n} assuming P⊈NPP \not\subseteq NP. It is not difficult to see that the same proof extends to (BC) and (TA) as well. On the positive side, (C), (BC), (BA), and (TA) admit (n−1)(n-1)-approximations and (L) has an (n2)\binom{n}{2}-approximation [20]. To the best of our knowledge, no better approximations are known.

In this paper, we study problems (B) and (C). As already mentioned above, there are several polynomial time minimization algorithms for (B) in the literature and they can be divided into two types. The ones from database theory [24] and hypergraphs [6, 7] use a local exchange lemma to decrease the number of bodies, utilizing an equivalence relation on the set of bodies. The algorithms from the closure systems literature [19, 4, 5] perform a sequence of steps, called right-saturation, left-saturation, and redundancy elimination to transform the input into an equivalent body-minimum representation. The latter approach produces a unique implication system representing the underlying Boolean function, which is called the GD-basis of the input. This name is derived from the initial letters of the authors’ names of [19].

In this paper we provide a first non-trivial polynomial time approximation algorithm for clause-minimization (problem (C)). Our result has three main components. First, in Section 3, we recall that there always exists a solution to problem (C) that has the same bodies as the unique GD-basis (which is computable in polynomial time). This result from [1, 9] immediately implies that the GD-basis constitutes a polynomial time (n−1)(n-1)-factor approximation for the clause minimization problem, matching the bound from [20]. Next, in Section 4, we show that the implication subsystem corresponding to the set of bodies with the same closure can be replaced, without destroying the logical equivalence with the underlying Horn function, by any other form using the same bodies and guaranteeing the same closure for those bodies. Finally, in Section 5 we provide a constructive approach to build such a replacement of ”small” size, yielding a polynomial time approximation algorithm which for any δ>0\delta> 0 outputs a (14+δ)n(\frac{1}{4}+\delta)n-factor approximation for problem (C).

Preliminaries

In this section, we introduce more notation to extend the definitions from the previous section, and show complexity results for several basic problems for implication systems.

For an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} let us denote by B(Φ)={Bi∣i∈[m]}\mathcal{B}(\Phi) = \{B_i \mid i \in[m]\} the set of bodies appearing in Φ\Phi, by ∥Φ∥=∑i=1m(∣Bi∣+∣Hi∣)\lVert\Phi\rVert= \sum_{i=1}^{m} (|B_i| + |H_i|) the size of Φ\Phi, and by cnf(Φ)=cn_f(\Phi) = ∑i=1m∣Hi∣\sum_{i=1}^{m} |H_i| the number of individual implications (clauses) in Φ\Phi.

An implication is a consequence of an implication system if it is satisfied by every satisfying assignment of the system. The following lemma, cited from the literature without proof, provides a condition for checking this property.

Lemma 2.1 ([20]) Let B→vB \to v be an implication and Φ\Phi an implication system. Then B→vB \to v is a logical consequence of Φ\Phi if and only if v∈CΦ(B)v \in C_{\Phi}(B). Furthermore, the closure CΦ(S)C_{\Phi}(S) can be computed in O(∥Φ∥)O(\lVert\Phi\rVert) time for every set S⊆VS \subseteq V.

Recall, that for a given implication system Φ\Phi we denote by C(Φ)={X⊆V∣CΦ(X)=X}C(\Phi) = \{X \subseteq V \mid C_{\Phi}(X) = X\} the set of its closed sets and we have Φ≡Ψ\Phi\equiv\Psi exactly when C(Φ)=C(Ψ)C(\Phi) = C(\Psi).

Lemma 2.2 For two implication systems Φ={Ai→Gi∣i∈[p]}\Phi= \{A_i \to G_i \mid i \in[p]\} and Ψ={Bj→Hj∣j∈[q]}\Psi= \{B_j \to H_j \mid j \in[q]\} we have Φ≡Ψ\Phi\equiv\Psi if and only if CΦ(Bj)⊇HjC_{\Phi}(B_j) \supseteq H_j for all j∈[q]j \in[q] and CΨ(Ai)⊇GiC_{\Psi}(A_i) \supseteq G_i for all i∈[p]i \in[p]. All these conditions can be tested in O(p∥Ψ∥+q∥Φ∥)O(p\lVert\Psi\rVert+ q\lVert\Phi\rVert) time.

Proof. Recall that X∈C(Φ)X \in C(\Phi) iff CΦ(X)=XC_{\Phi}(X) = X, and analogously, Y∈C(Ψ)Y \in C(\Psi) iff CΨ(Y)=YC_{\Psi}(Y) = Y. Consequently, the first part of the statement follows by the above definitions and the definition of equivalence. The complexity claim follows by Lemma 2.1 since the above inclusions can be tested in O(∥Ψ∥)O(\lVert\Psi\rVert) time for every rule in Φ\Phi and in O(∥Φ∥)O(\lVert\Phi\rVert) time for every rule in Ψ\Psi.

Functional properties of implication subsystems

For an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} and subset I⊆[m]I \subseteq[m] we say that Ψ={Bi→Hi∣i∈I}\Psi= \{B_i \to H_i \mid i \in I\} is an implication subsystem of Φ\Phi. We will write Φ∖Ψ={Bi→Hi∣i∈[m]∖I}\Phi\setminus\Psi= \{B_i \to H_i \mid i \in[m] \setminus I\} and Φ=(Φ∖Ψ)∪Ψ\Phi= (\Phi\setminus\Psi) \cup\Psi. In other words, we view implication systems as sets of rules.

To an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} and subset S⊆VS \subseteq V we associate the following implication subsystem

Φ⊆S={Bi→Hi∣i∈[m],CΦ(Bi)⊆CΦ(S)}Φ⊂S={Bi→Hi∣i∈[m],CΦ(Bi)⊂CΦ(S)}Φ=S={Bi→Hi∣i∈[m],CΦ(Bi)=CΦ(S)}Φ≠S={Bi→Hi∣i∈[m],CΦ(Bi)≠CΦ(S)}.\begin{aligned} \Phi_{\subseteq S} &= \{B_i \to H_i \mid i \in[m], C_{\Phi}(B_i) \subseteq C_{\Phi}(S)\}\\ \Phi_{\subset S} &= \{B_i \to H_i \mid i \in[m], C_{\Phi}(B_i) \subset C_{\Phi}(S)\}\\ \Phi_{=S} &= \{B_i \to H_i \mid i \in[m], C_{\Phi}(B_i) = C_{\Phi}(S)\}\\ \Phi_{\ne S} &= \{B_i \to H_i \mid i \in[m], C_{\Phi}(B_i) \ne C_{\Phi}(S)\}. \end{aligned}

These subsystems have important functional properties, which we show in the following lemmas.

Lemma 3.1 If Φ≡Ψ\Phi\equiv\Psi are equivalent implication systems, then for all subsets S⊆VS \subseteq V we have Φ⊂S≡Ψ⊂S\Phi_{\subset S} \equiv\Psi_{\subset S}.

Proof. We are going to prove the claim by Lemma 2.2. Let us consider an arbitrary subset S⊆VS \subseteq V. Since in the claim the role of Φ\Phi and Ψ\Psi are symmetric, it is enough to show that for all rules B→HB \to H of Φ⊂S\Phi_{\subset S} we have CΨ⊂S(B)⊇HC_{\Psi_{\subset S}}(B) \supseteq H. By the definition of Φ⊂S\Phi_{\subset S} we have CΦ(B)⊂CΦ(S)C_{\Phi}(B) \subset C_{\Phi}(S) implying that for all rules Bi→HiB_i \to H_i used in deriving CΦ(B)C_{\Phi}(B) we have CΦ(Bi)⊂CΦ(S)C_{\Phi}(B_i) \subset C_{\Phi}(S) implying CΦ⊂S(B)=CΦ(B)C_{\Phi_{\subset S}}(B) = C_{\Phi}(B). Thus we have CΦ(S)⊃CΦ⊂S(B)=CΦ(B)=CΨ(B)C_{\Phi}(S) \supset C_{\Phi_{\subset S}}(B) = C_{\Phi}(B) = C_{\Psi}(B), where the last equality follows by the equivalence of Φ\Phi and Ψ\Psi. Consequently, all rules of Ψ\Psi used to derive CΨ(B)C_{\Psi}(B) are also rules of Ψ⊂S\Psi_{\subset S} implying CΦ⊂S(B)=CΦ(B)=CΨ(B)=CΨ⊂S(B)C_{\Phi_{\subset S}}(B) = C_{\Phi}(B) = C_{\Psi}(B) = C_{\Psi_{\subset S}}(B). Since H⊆CΦ⊂S(B)H \subseteq C_{\Phi_{\subset S}}(B) by the choice of the rule B→HB \to H, the claim follows.

Lemma 3.2. For two implication systems, Φ\Phi and Ψ\Psi we have Φ≡Ψ\Phi\equiv\Psi if and only if Φ⊆S≡Ψ⊆S\Phi_{\subseteq S} \equiv\Psi_{\subseteq S} holds for all subsets S⊆VS \subseteq V.

Proof. The “if” part of the claim follows by the simple facts that Φ=Φ⊆V\Phi= \Phi_{\subseteq V} and Ψ=Ψ⊆V\Psi= \Psi_{\subseteq V}. The “only if” part follows by an analogous proof as in the previous lemma, replacing all ⊊\subsetneq relations in that proof by ⊆\subseteq.

Lemma 3.3. For an implication system Φ\Phi and a subset S⊆VS \subseteq V we have CΦ≠S(T)=CΦ⊂S(T)C_{\Phi\ne S}(T) = C_{\Phi\subset S}(T) for all subsets T⊆CΦ(S)T \subseteq C_{\Phi}(S).

Proof. Note that Φ⊂S\Phi_{\subset S} is an implication subsystem of Φ≠S\Phi_{\ne S} which is an implication subsystem of Φ\Phi, implying by the definition of the closure operator that

CΦ⊂S(T)⊆CΦ≠S(T)⊆CΦ(T)(2)C_{\Phi\subset S}(T) \subseteq C_{\Phi\ne S}(T) \subseteq C_{\Phi}(T) \tag*{(2)}

for all subsets T⊆VT \subseteq V. Since T⊆CΦ(S)T \subseteq C_{\Phi}(S) we also have

CΦ(T)⊆CΦ(S)C_{\Phi}(T) \subseteq C_{\Phi}(S)

by the properties of a closure operator. Consequently for all implications Bi→HiB_i \to H_i used in deriving CΦ≠S(T)C_{\Phi\ne S}(T) we have Bi⊆CΦ≠S(T)B_i \subseteq C_{\Phi\ne S}(T) and consequently by the above relations and the properties of the closure operation we have CΦ(Bi)⊆CΦ(S)C_{\Phi}(B_i) \subseteq C_{\Phi}(S). The nonequality CΦ(Bi)≠CΦ(S)C_{\Phi}(B_i) \ne C_{\Phi}(S) follows by the definition of Φ≠S\Phi_{\ne S}, implying CΦ(Bi)⊊CΦ(S)C_{\Phi}(B_i) \subsetneq C_{\Phi}(S), from which it follows that we have equality in the first inequality of (2).

Lemma 3.4. For an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} and index j∈[m]j \in[m] we define Ψ=(Φ∖{Bj→Hj})∪{CΦ≠Bj(Bj)→Hj}\Psi= (\Phi\setminus\{B_j \to H_j\}) \cup\{C_{\Phi\ne B_j}(B_j) \to H_j\}. Then we have Φ≡Ψ\Phi\equiv\Psi.

Proof. We can apply Lemma 2.2 which in this special case implies that we have Φ≡Ψ\Phi\equiv\Psi if and only if CΨ(Bj)⊇HjC_{\Psi}(B_j) \supseteq H_j. Note next that Φ≠Bj\Phi_{\ne B_j} is an implication subsystem of Φ∖{Bj→Hj}\Phi\setminus\{B_j \to H_j\} and thus it is an implication subsystem of Ψ\Psi. Consequently, we have CΨ(Bj)⊇CΦ≠Bj(Bj)C_{\Psi}(B_j) \supseteq C_{\Phi\ne B_j}(B_j) from which CΨ(Bj)⊇HjC_{\Psi}(B_j) \supseteq H_j follows by the definition of Ψ\Psi.

To an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} we associate

Φ∙={CΦ≠Bi(Bi)→Hi∣i∈[m]}\Phi^{\bullet} = \{C_{\Phi\ne B_i}(B_i) \to H_i \mid i \in[m]\}

and call it the left-saturation of Φ\Phi.

Corollary 3.5. For every implication system Φ\Phi we have Φ≡Φ∙\Phi\equiv\Phi^{\bullet}.

Proof. Follows by the sequential application of Lemma 3.4.

To an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} we associate

Φ∗={Bi→CΦ(Bi)∣i∈[m]}\Phi^{*} = \{B_i \to C_{\Phi}(B_i) \mid i \in[m]\}

and call it the right-saturation of Φ\Phi.

Lemma 3.6. For every implication system Φ\Phi we have Φ≡Φ∗\Phi\equiv\Phi^{*}.

Proof. Immediate by Lemma 2.2.

Let us finally associate to an implication system Φ\Phi the implication system Φ∗\Phi^{\ast} obtained from (Φ∙)∗(\Phi^{\bullet})^{\ast} by eliminating the redundant rules. Let us point out that if Φ\Phi is an irredundant implication system, then its left saturation will also be irredundant. However, it may contain rules that become redundant after right saturation. More precisely, introducing Bi∙=CΦ≠Bi(Bi)=CΦ⊂Bi(Bi)B_i^{\bullet} = C_{\Phi\ne B_i}(B_i) = C_{\Phi\subset B_i}(B_i) (where the second equality holds by Lemma 3.3) we may have pairs of rules in Φ∙\Phi^{\bullet} such that

Bj∙⊆Bi∙andCΦ(Bi)=CΦ(Bj)for some i≠j∈[m].(3)B_j^{\bullet} \subseteq B_i^{\bullet} \quad\text{and}\quad C_{\Phi}(B_i) = C_{\Phi}(B_j) \quad\text{for some } i \ne j \in[m]. \tag*{(3)}

In this case, rule ii can be replaced by rule jj extended with the heads of rule ii without losing equivalence with the underlying function. For details and a full proof we refer the reader to [24].

Theorem 3.7 ([19, 4, 5]) For an implication system Φ\Phi the associated implication system Φ∗\Phi^{\ast} is a unique body-minimum representation of the underlying Horn function, called its GD-basis.

Note that the GD-basis Φ∗\Phi^{\ast} can be computed in O(m∥Φ∥)O(m\lVert\Phi\rVert) time from any implication system Φ\Phi representing the same underlying Horn function, see e.g., [19, 4, 5].

The next theorem plays an important role in our constructive approximation result, and thus, for completeness, we include here a short proof, which utilizes the above structural results of implications subsystems, and is slightly different from the proofs in the literature.

Theorem 3.8 ([1, 9]) Every implication system Φ\Phi has a clause-minimum representation Σ\Sigma such that B(Σ)=B(Φ∗)\mathcal{B}(\Sigma) = \mathcal{B}(\Phi^{\ast}).

Proof. Let Ψ={Bi→Hi∣i∈[m]}\Psi= \{B_i \to H_i \mid i \in[m]\} be an arbitrary clause-minimum representation of Φ\Phi and define Π=Ψ∙={Bi∙→Hi∣i∈[m]}\Pi= \Psi^{\bullet} = \{B_i^{\bullet} \to H_i \mid i \in[m]\}. Note that Ψ\Psi is an irredundant system, and thus Π\Pi is also irredundant (see e.g., [4, 5]). Then by Corollary 3.5 we have Π≡Ψ\Pi\equiv\Psi. Furthermore, by the definition of the left-saturation, we have cnf(Π)=cnf(Ψ)cnf(\Pi) = cnf(\Psi). As we noted above, Π\Pi may contain pairs of rules as in (3). In such a case, we can replace Bi∙→HiB_i^{\bullet} \to H_i and Bj∙→HjB_j^{\bullet} \to H_j by Bj∙→Hi∪HjB_j^{\bullet} \to H_i \cup H_j which by Lemma 2.2 preserves the equivalence with the underlying function (see also [24]). Since Ψ\Psi is clause-minimum, we must have Hi∩Hj=∅H_i \cap H_j = \varnothing, and thus this operation does not change the number of clauses. After eliminating all such pairs, we arrive at an implication system Σ\Sigma for which we have Σ≡Ψ\Sigma\equiv\Psi, cnf(Σ)=cnf(Ψ)cnf(\Sigma) = cnf(\Psi) and B(Σ)=B(Ψ∗)\mathcal{B}(\Sigma) = \mathcal{B}(\Psi^{\ast}), where the last equality follows by the definition of the GD basis.

Corollary 3.9 ([1, 9]) Given an implication system Ψ\Psi there exists an equivalent implication system Φ\Phi which is both clause-minimum and body-minimum.

Proof. Follows directly by Theorem 3.8.

Decompositions and substitutions

In this section, we provide a number of results about substituting an implication subsystem by another implication system without losing equivalence with the underlying Horn function.

Lemma 4.1 Assume Π\Pi, Φ\Phi and Ψ\Psi are implications systems such that Π=Φ∪Ψ\Pi= \Phi\cup\Psi. Then we have C(Π)=C(Φ)∩C(Ψ)\mathcal{C}(\Pi) = \mathcal{C}(\Phi) \cap\mathcal{C}(\Psi).

Proof. Follows directly from the definition of a closed set.

Lemma 4.2 Assume Φ=Φ′∪Φ′′\Phi= \Phi^{\prime} \cup\Phi^{\prime\prime} and Φ′′≡Ψ\Phi^{\prime\prime} \equiv\Psi. Then we have Φ′∪Ψ≡Φ\Phi^{\prime} \cup\Psi\equiv\Phi.

Proof. By Lemma 4.1 and our assumptions, we have C(Φ)=C(Φ′)∩C(Φ′′)\mathcal{C}(\Phi) = \mathcal{C}(\Phi^{\prime}) \cap\mathcal{C}(\Phi^{\prime\prime}) and C(Φ′′)=C(Ψ)\mathcal{C}(\Phi^{\prime\prime}) = \mathcal{C}(\Psi) from which C(Φ′)∩C(Ψ)=C(Φ)\mathcal{C}(\Phi^{\prime}) \cap\mathcal{C}(\Psi) = \mathcal{C}(\Phi) follows, proving the equivalence as claimed.

Lemma 4.2 shows that an implication subsystem can be replaced by an equivalent expression, preserving equivalence of the implication system. The next lemma shows that certain subsystems can be switched to another expression preserving equivalence of the implication system, even if the switched expressions themselves are not necessarily equivalent.

Lemma 4.3 Assume Φ≡Ψ\Phi\equiv\Psi and S⊆VS \subseteq V. Then for

Σ=Φ⊈S∪Ψ⊆S∪(Φ∖Φ⊆S)\Sigma= \Phi_{\not\subseteq S} \cup\Psi_{\subseteq S} \cup(\Phi\setminus\Phi_{\subseteq S})

we have Σ≡Φ\Sigma\equiv\Phi.

Proof. Let us consider Π=Ψ⊆S∪(Φ∖Φ⊆S)\Pi= \Psi_{\subseteq S} \cup(\Phi\setminus\Phi_{\subseteq S}). By Lemma 3.2 we have Π≡Φ\Pi\equiv\Phi. Then we have Σ=Φ⊆S∪(Π∖Π⊆S)\Sigma= \Phi_{\subseteq S} \cup(\Pi\setminus\Pi_{\subseteq S}), and thus Σ≡Π≡Φ\Sigma\equiv\Pi\equiv\Phi follows by Lemma 3.1.

The next lemma proves the interesting property that a clause minimum implication system is also locally minimum for certain subsystems.

Lemma 4.4 Given an implication system Φ\Phi, consider a clause-minimum Ψ≡Φ\Psi\equiv\Phi. Then for every S⊆VS \subseteq V we have

cnf⁡(Ψ⊆S)=min⁡Π≡Ψcnf⁡(Π⊆S)=min⁡Π≡Ψ⊆Scnf⁡(Π⊆S).\operatorname{cnf}(\Psi_{\subseteq S}) = \min_{\Pi\equiv\Psi} \operatorname{cnf}(\Pi_{\subseteq S}) = \min_{\Pi\equiv\Psi_{\subseteq S}} \operatorname{cnf}(\Pi_{\subseteq S}).

Proof. Assume for a contradiction that there exists a Π≡Φ\Pi\equiv\Phi such that cnf⁡(Π⊆S)<cnf⁡(Ψ⊆S)\operatorname{cnf}(\Pi_{\subseteq S}) < \operatorname{cnf}(\Psi_{\subseteq S}) for some S⊆VS \subseteq V. Then by Lemma 4.3 the implication system

Σ=Ψ⊈S∪Π⊆S∪(Ψ∖Ψ⊆S)\Sigma= \Psi_{\not\subseteq S} \cup\Pi_{\subseteq S} \cup(\Psi\setminus\Psi_{\subseteq S})

is equivalent with Ψ\Psi and has

cnf⁡(Σ)=cnf⁡(Ψ⊈S)+cnf⁡(Π⊆S)+cnf⁡(Ψ∖Ψ⊆S)<cnf⁡(Ψ)\operatorname{cnf}(\Sigma) = \operatorname{cnf}(\Psi_{\not\subseteq S}) + \operatorname{cnf}(\Pi_{\subseteq S}) + \operatorname{cnf}(\Psi\setminus\Psi_{\subseteq S}) < \operatorname{cnf}(\Psi)

contradicting the clause-minimality of Ψ\Psi. This contradiction proves the first equality. The second equality follows by Lemmas 3.2 and 4.2.

Finally, the next lemma proves an exchange property which is crucial for the approximation algorithm in the next section.

Lemma 4.5. Let us consider an implication system Φ\Phi, a body B∈B(Φ)B \in\mathcal{B}(\Phi) and another implication system Ψ\Psi such that B(Ψ)=B(Φ⊆B)\mathcal{B}(\Psi) = \mathcal{B}(\Phi_{\subseteq B}) and CΨ(B′)=CΦ(B′)C_{\Psi}(B') = C_{\Phi}(B') holds for every B′∈B(Φ⊆B)B' \in\mathcal{B}(\Phi_{\subseteq B}). Then

Π=Φ⊆B∪Ψ∪(Φ∖Φ⊆B)\Pi= \Phi_{\subseteq B} \cup\Psi\cup(\Phi\setminus\Phi_{\subseteq B})

is equivalent to Φ\Phi.

Proof. Let us note that Φ∗≡Φ\Phi^{*} \equiv\Phi by Lemma 3.6, and we have Ψ≡Φ⊆B∗\Psi\equiv\Phi^{*}_{\subseteq B} by Lemma 2.2. Thus

Φ≡Π=Φ⊆B∗∪Ψ∪(Φ∗∖Φ⊆B∗)\Phi\equiv\Pi= \Phi^{*}_{\subseteq B} \cup\Psi\cup(\Phi^{*} \setminus\Phi^{*}_{\subseteq B})

by Lemma 4.2, and therefore the claim follows by Lemma 4.3 applied to Φ\Phi and Π\Pi.

Approximation for clause minimization

In this section, we present an approximation algorithm for the clause minimization problem. By Theorem 3.8 the clause minimization problem for an implication system Φ={Bi→Hi∣i∈[m]}\Phi= \{B_i \to H_i \mid i \in[m]\} is equivalent to finding a clause-minimum implication system, logically equivalent to Φ\Phi, the bodies of which are the bodies of the GD-basis of Φ\Phi. Since the GD-basis can be computed efficiently, in the rest of this section we assume that Φ=Φ∗\Phi= \Phi^{*} is the input to the approximation algorithm. This allows a constructive approach which iteratively replaces subsystems in a way that preserves logical equivalence of the entire implication system. In particular, Lemmas 4.3, 4.4 and 4.5 will be instrumental in our arguments.

To an implication system Φ=Φ∗\Phi= \Phi^{*} let us associate the family of body closures:

H(Φ)={CΦ(B)∣B∈B(Φ)}.\mathcal{H}(\Phi) = \{C_{\Phi}(B) \mid B \in\mathcal{B}(\Phi)\}.

For H∈H(Φ)H \in\mathcal{H}(\Phi) we define

ΦH={B→H∖B∣B∈B(Φ), CΦ(B)=H}.\Phi_H = \{B \to H \setminus B \mid B \in\mathcal{B}(\Phi),\ C_{\Phi}(B) = H\}.

Using this notation, Φ\Phi can be decomposed into subsystems

Φ=⋃H∈H(Φ)ΦH.\Phi= \bigcup_{H \in\mathcal{H}(\Phi)} \Phi_H.

In our approximation algorithm, we apply two different constructions to replace each subsystem ΦH\Phi_H by another implication system ΨH\Psi_H such that Φ≡(Φ∖ΦH)∪ΨH\Phi\equiv(\Phi\setminus\Phi_H) \cup\Psi_H. Let us also introduce

OPT⁡H=min⁡Π≡Φcnf⁡(Π≡H)andOPT⁡=min⁡Π≡Φcnf⁡(Π)=∑H∈H(Φ)OPT⁡H.\operatorname{OPT}_H = \min_{\Pi\equiv\Phi} \operatorname{cnf}(\Pi_{\equiv H}) \quad\text{and} \quad\operatorname{OPT} = \min_{\Pi\equiv\Phi} \operatorname{cnf}(\Pi) = \sum_{H \in\mathcal{H}(\Phi)} \operatorname{OPT}_H.

If Π\Pi is an arbitrary clause-minimum implication system of Φ\Phi, then we have cnf⁡(Π)=OPT⁡\operatorname{cnf}(\Pi) = \operatorname{OPT} and cnf⁡(Π≡H)=OPT⁡H\operatorname{cnf}(\Pi_{\equiv H}) = \operatorname{OPT}_H for all H∈H(Φ)H \in\mathcal{H}(\Phi) by Lemma 4.4, which also justifies the last equality in the formula above.

Procedure 1

Let us assume that we focus on such a subsystem ΦH\Phi_H for some H∈H(Φ)H \in\mathcal{H}(\Phi), as defined above. Assume that B(ΦH)={Bi∣i∈[p]}\mathcal{B}(\Phi_H)=\{B_i \mid i \in[p]\}, p≥2p \ge2 is the family of bodies which are of course subsets of HH. Let αij=∣Bi∖Bj∣\alpha_{ij}=|B_i \setminus B_j| for any pair of distinct indices i,j∈[p]i,j \in[p], and define α∗=min⁡i∈H∑j∈[p],j≠iαij\alpha^*=\min_{i\in H}\sum_{j\in[p],j\ne i}\alpha_{ij}.

Our first procedure is based on the following lemma.

Lemma 5.1 α∗≤∣H∣p4\alpha^* \le\frac{|H|p}{4}.

Proof. For any S⊆[p]S \subseteq[p], let US=(⋂i∈SBi)∩(⋂i∉S(H∖Bi))U_S=\left(\bigcap_{i\in S}B_i\right)\cap\left(\bigcap_{i\notin S}(H\setminus B_i)\right). Note that these sets form a partition of HH. We then have

pα∗≤∑i,j∈[p]i≠jαij=∑S⊆[p](p−∣S∣)∣S∣∣US∣.(4)p\alpha^* \le\sum_{\substack{i,j\in[p]\\i\ne j}}\alpha_{ij}=\sum_{S\subseteq[p]}(p-|S|)|S||U_S|. \tag*{(4)}

If pp is even, the right-hand side of (4) is bounded by p24∑S⊆[p]∣US∣=∣H∣p2/4\frac{p^2}{4}\sum_{S\subseteq[p]}|U_S|=|H|p^2/4, which implies the stated inequality.

On the other hand, if pp is odd, the right-hand side of (4) is bounded by ((p+1)(p−1)∑S⊆[p]∣US∣)/4=(p+1)(p−1)∣H∣/4≤∣H∣p2/4((p+1)(p-1)\sum_{S\subseteq[p]}|U_S|)/4=(p+1)(p-1)|H|/4\le|H|p^2/4, which again implies the claim.

:::

1st Approximate Clause-Minimum

Input: An implication system ΦH={Bi→H∖Bi∣i∈[p]}\Phi_H=\{B_i\to H\setminus B_i\mid i\in[p]\}.

Step 1: Compute an index i∗∈[p]i^*\in[p] such that α∗=∑j∈[p],j≠i∗αi∗j\alpha^*=\sum_{j\in[p],j\ne i^*}\alpha_{i^*j}.

Step 2: Output ΨH={Bi→Bi∗∖Bi∣i∈[p]∖{i∗}}∪{Bi∗→H∖Bi∗}\Psi_H=\{B_i\to B_{i^*}\setminus B_i\mid i\in[p]\setminus\{i^*\}\}\cup\{B_{i^*}\to H\setminus B_{i^*}\}.

Lemma 5.2 The above procedure computes in O(p2∣H∣)O(p^2|H|) time an implication system ΨH\Psi_H equivalent to ΦH\Phi_H such that

cnf(ΨH)≤(14+1p)∣H∣⋅p≤(14+1p)∣H∣⋅OPTH.cnf(\Psi_H)\le\left(\frac{1}{4}+\frac{1}{p}\right)|H|\cdot p\le\left(\frac{1}{4}+\frac{1}{p}\right)|H|\cdot OPT_H.

Proof. By its definition, we have CΨH(Bi)=HC_{\Psi_H}(B_i)=H for all i∈[p]i\in[p], consequently ΨH≡ΦH\Psi_H\equiv\Phi_H follows by Lemma 2.2. Furthermore, by Lemma 5.1 we have

cnf(ΨH)=α∗+∣H∖Bi∗∣≤∣H∣p4+∣H∣≤(14+1p)∣H∣⋅pcnf(\Psi_H)=\alpha^*+|H\setminus B_{i^*}|\le\frac{|H|p}{4}+|H|\le\left(\frac{1}{4}+\frac{1}{p}\right)|H|\cdot p

as claimed. Note finally that OPTH≥pOPT_H\ge p, since each body of ΦH\Phi_H must have at least one head in every equivalent representation, implying the second inequality.

Procedure 2

Since the previous approach may not provide a good enough approximation ratio when pp is not large enough, we also consider another, much simpler exhaustive procedure.

2nd Approx Clause-Minimum

Input: An implication system ΦH={Bi→H∖Bi∣i∈[p]}\Phi_H = \{B_i \to H \setminus B_i \mid i \in[p]\} and a constant cc, where we assume that ∣H∣≥c|H| \ge c.

Step 1: Search exhaustively for hypergraphs {Hi⊆H∖Bi∣i∈[p]}\{H_i \subseteq H \setminus B_i \mid i \in[p]\} such that

∑i∣Hi∣≤cpandΦ⊆H≡Φ⊂H∪{Bi→Hi∣i∈[p]}.\sum_i |H_i| \le cp \quad\text{and}\quad\Phi_{\subseteq H} \equiv\Phi_{\subset H} \cup\{B_i \to H_i \mid i \in[p]\}.

Step 2: If such hypergraphs exist, choose one with the smallest ∑i∣Hi∣\sum_i |H_i| and define ΨH={Bi→Hi∣i∈[p]}\Psi_H = \{B_i \to H_i \mid i \in[p]\}, otherwise, define ΨH=ΦH\Psi_H = \Phi_H.

Step 3: Output ΨH\Psi_H.

Lemma 5.3 The above procedure computes in O((np)cpp∥Φ∥)O((np)^{cp}p\|\Phi\|) time an implication system ΨH\Psi_H on nn variables such that Φ⊆H≡Φ⊂H∪ΨH\Phi_{\subseteq H} \equiv\Phi_{\subset H} \cup\Psi_H and

cnf(ΨH)≤∣H∣cOPTH.cnf(\Psi_H) \le\frac{|H|}{c}OPT_H.

Proof. It is not difficult to see that Step 1 in the above procedure can be performed by checking O((np)cp)O((np)^{cp}) many cases. In each case we need to check the stated equivalence, which is equivalent by Lemma 2.2 to check for each i∈[p]i \in[p] if the closure of BiB_i by the constructed implication form is indeed HH. For each case this takes O(p∥Φ∥)O(p\|\Phi\|) time. If there is a solution in Step 1, then by Lemma 4.4 we have cnf(ΨH)=OPTH≤∣H∣cOPTHcnf(\Psi_H) = OPT_H \le\frac{|H|}{c}OPT_H by our assumption ∣H∣≥c|H| \ge c. On the other hand, if no solution is found in Step 1, then we have OPTH>cpOPT_H > cp again by Lemma 4.4, and thus for the output ΨH=ΦH\Psi_H = \Phi_H we have cnf(ΦH)≤p∣H∣=∣H∣cpc<∣H∣cOPTHcnf(\Phi_H) \le p|H| = \frac{|H|}{c}pc < \frac{|H|}{c}OPT_H, proving the claim.

Polynomial time approximation algorithm

Now we are ready to state our main approximation result for clause minimization.

Theorem 5.4 Given an implication system Σ\Sigma on nn variables and a constant δ>0\delta> 0, we can compute in polynomial time an implication system Ψ≡Σ\Psi\equiv\Sigma such that

cnf(Ψ)≤(14+δ)n⋅min⁡Π≡Σcnf(Π)=(14+δ)n⋅OPT.cnf(\Psi) \le\left(\frac{1}{4}+\delta\right)n \cdot\min_{\Pi\equiv\Sigma} cnf(\Pi) = \left(\frac{1}{4}+\delta\right)n \cdot OPT.

Proof. Let us assume n≥8n \ge8 since otherwise we can compute the clause minimum form in constant time.

Assume m=∣B(Σ)∣m = |\mathcal{B}(\Sigma)| and let Φ=Σ∗\Phi= \Sigma^{\ast} be the GD-basis of Σ\Sigma. By [4, 5] it can be computed in O(m∥Σ∥)O(m\|\Sigma\|) time from Σ\Sigma.

Let us consider, as above, the closures of the bodies of the GD-basis, and define

H1(Φ)={H∈H(Φ)∣∣B(Φ≡H)∣>1/δ}\mathcal{H}_1(\Phi) = \{H \in\mathcal{H}(\Phi) \mid|\mathcal{B}(\Phi_{\equiv H})| > 1/\delta\}
H2(Φ)={H∈H(Φ)∣∣B(Φ≡H)∣≤1/δ}.\mathcal{H}_2(\Phi) = \{H \in\mathcal{H}(\Phi) \mid|\mathcal{B}(\Phi_{\equiv H})| \le1/\delta\}.

For H∈H1(Φ)H \in\mathcal{H}_1(\Phi) we compute ΨH\Psi_H by the first procedure and obtain by Lemma 5.2 that

cnf(ΨH)OPTH≤(14+1∣B(Φ=H)∣)∣H∣<(14+δ)∣H∣.\frac{cnf(\Psi_H)}{OPT_H} \leq\left(\frac{1}{4}+\frac{1}{|\mathcal{B}(\Phi_{=H})|}\right)|H| < \left(\frac{1}{4}+\delta\right)|H|.

For H∈H2(Φ)H \in\mathcal{H}_2(\Phi), ∣H∣≥4|H| \geq4, we apply the second procedure with c=4c=4 to obtain ΨH\Psi_H for which by Lemma 5.3 we have

cnf(ΨH)OPTH≤∣H∣4.\frac{cnf(\Psi_H)}{OPT_H} \leq\frac{|H|}{4}.

For H∈H2(Φ)H \in\mathcal{H}_2(\Phi) such that ∣H∣<4|H| < 4 we can choose ΨH=ΦH\Psi_H=\Phi_H because then we automatically have

cnf(ΨH)OPTH≤2≤n4.\frac{cnf(\Psi_H)}{OPT_H} \leq2 \leq\frac{n}{4}.

by our assumption n≥8n \geq8.

Since cnf(Ψ)=∑H∈H(Φ)cnf(ΨH)cnf(\Psi)=\sum_{H\in\mathcal{H}(\Phi)}cnf(\Psi_H) and OPT=∑H∈H(Φ)OPTHOPT=\sum_{H\in\mathcal{H}(\Phi)}OPT_H we get

cnf(Ψ)OPT≤max⁡H∈H(Φ)cnf(ΨH)OPTH≤(14+δ)n\frac{cnf(\Psi)}{OPT} \leq\max_{H\in\mathcal{H}(\Phi)}\frac{cnf(\Psi_H)}{OPT_H} \leq\left(\frac{1}{4}+\delta\right)n

proving the claimed inequality.

In our computations, the dominant part is the execution of Step 1 in the second procedure, which for p≤1/δp\leq1/\delta and c=4c=4 requires O(n4/δ∥Φ∥)O(n^{4/\delta}\|\Phi\|) time.

References

  1. [1]K. Adaricheva and J.B. Nation On implicational bases of closure systems with unique critical sets Discrete Applied Mathematics, volume 162, pages 51-69, 2014. doi.org/10.1016/j.dam.2013.08.033DOI
  2. [2]A.V. Aho, M.R. Garey, and J.D. Ullman The transitive reduction of a directed graph. SIAM Journal on Computing, 1:2, pages 131–137, 1972, SIAM.DOI
  3. [3]W. W. Armstrong. Dependency structures of database relationships. Proc. IFIP 74. North Holland, Amsterdam, 1974, pp. 580-583.
  4. [4]M. Arias and J.L. Balcázar. Canonical Horn representations and query learning. In Ricard Gavaldà, Gábor Lugosi, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory, volume 5809 of Lecture Notes in Computer Science, pages 156–170. Springer Berlin Heidelberg, 2009.DOI
  5. [5]M. Arias and J.L. Balcázar. Construction and learnability of canonical Horn formulas. Machine Learning, 85(3):273–297, 2011.DOI
  6. [6]G. Ausiello, A. D’Atri, and D. Sacca. Graph algorithms for functional dependency manipulation. J. Assoc. Comp. Mach., 30: 752–766, 1983.
  7. [7]G. Ausiello, A. D’Atri, and D. Sacca. Minimal representation of directed hypergraphs. SIAM Journal on Computing, 15(2):418–431, 1986.
  8. [8]C. Beeri and P.A. Bernstein. Computational problems related to the design of normal form relational schemas. ACM Trans Database Syst 4(1): 30–59, 1979.DOI
  9. [9]K. Bérczi and E.R. Bérczi-Kovács. Directed hypergraphs and Horn minimization. Information Processing Letters 128: 32–37, 2017.DOI
  10. [10]K. Bérczi, E. Boros, O. Čepek, P. Kučera, and K. Makino. Approximating minimum representations of key Horn functions, SIAM J. Comput. 51: 116–138, 2022.arxiv.org/abs/1811.05160
  11. [11]A. Bhattacharya, B. DasGupta, D. Mubayi, and G. Turán. On approximate Horn formula minimization. International Colloquium on Automata, Languages, and Programming (ICALP), pages 438–450, 2010, Springer.DOI
  12. [12]E. Boros, O. Čepek, and A. Kogan. Horn minimization by iterative decomposition. Annals of Mathematics and Artificial Intelligence, 23(3-4):321–343, 1998.
  13. [13]E. Boros, O. Čepek, A. Kogan, and P. Kučera. A subclass of Horn CNFs optimally compressible in polynomial time. Ann. Math. Artif. Intell., 57(3-4):249–291, 2009.DOI
  14. [14]E. Boros, O. Čepek, A. Kogan, and P. Kučera. Exclusive and essential sets of implicates of Boolean functions. Discrete Appl. Math., 158(2):81–96, 2010.DOI
  15. [15]E. Boros, O. Čepek, and P. Kučera. A decomposition method for CNF minimality proofs. Theoretical Computer Science, 510:111–126, 2013.DOI
  16. [16]E. Boros and A. Gruber. Hardness results for approximate pure Horn CNF formulae minimization. Annals of Mathematics and Artificial Intelligence, 71:4, pages 327–363, 2014, Springer.
  17. [17]Y. Crama and P.L. Hammer. Boolean Functions: Theory, Algorithms, and Applications. Cambridge (Encyclopedia of Mathematics and its Applications), 2011.
  18. [18]R. Fagin. Horn clauses and database dependencies. Journal of the Association for Computing Machinery, VoL 29(4), October 1982, pp 952-985.DOI
  19. [19]J.L. Guigues and V. Duquenne. Familles minimales d´implications informatives résultant d´ une tables de données binaires. Math. Sci. Hum., 95:5–18, 1986.
  20. [20]P.L. Hammer and A. Kogan. Optimal compression of propositional Horn knowledge bases: complexity and approximation. Artificial Intelligence, 64(1):131–145, 1993.DOI
  21. [21]P.L. Hammer and A. Kogan. Quasi-acyclic propositional Horn knowledge bases: optimal compression. Knowledge and Data Engineering, IEEE Transactions on, 7(5):751–762, Oct 1995.DOI
  22. [22]A. Horn. On sentences which are true of direct unions of algebras. Journal of Symbolic Logic, 16:14–21, 1951.DOI
  23. [23]P. Kučera. Hydras: Complexity on general graphs and a subclass of trees, Theoret. Comput. Sci., 658 (2017), pp. 399–416.DOI
  24. [24]D. Maier. Minimum covers in relational database model. J. ACM, 27(4):664–674, October 1980.DOI
  25. [25]J. McKinsey. The decision problem for some classes of sentences without classifiers. Journal of Symbolic Logic, 8:61–76, 1943.DOI
  26. [26]M. Wild. A theory of finite closure spaces based on implications. Advances in Mathematics, 108(1):118 – 139, 1994.DOI

Paper details

vlnc:W_dbm6frrs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents