We study existence of a restricted least general generalization (LGG) with the property that LGGs of clauses from a pre- xed set belong to this set. We show that there is no such LGG even in simple sets of clauses such as bounded-size clauses or treewidth-1 clauses. In this paper we study restricted forms of least general generalization (LGG) [6]. One such restricted form of LGG called bounded LGG was introduced in [4]. The main di erence between ordinary LGG of some clauses A1; A2; : : : ; Ak and their bounded LGG w.r.t. a set X is that the latter type of LGG does not have to be the least general of all generalizations of these clauses, it merely su ces if it is less general than any other generalization from X . In [3], it has been shown that bounded LGG can be used for hypothesis learning without having to resort to using exponential-time algorithms for -subsumption if we allow the algorithm to potentially miss some hypotheses not from the set X (e.g. some high-treewidth hypotheses). One property of bounded LGG was, however, still asking for a further study. When computing bounded LGG w.r.t. a set X , it may often be the case that the resulting clause will not be from the set X . For instance, when X consists of clauses of treewidth bounded by k, it may be the case that a bounded LGG of some clauses w.r.t. this set will have treewidth higher than k even if the clauses to be generalized are all from the set X as well. The question was whether there could be another type of restricted LGG which would not have this property, at least for some reasonable sets X . We study this question in this paper and answer it negatively even for simple sets X .
equivalent to it. A tree-decomposition [
A rst-order-logic clause is a universally quanti ed disjunction of rst-orderlogic literals. For convenience, we do not write the universal quanti ers explicitly. We treat clauses as disjunctions of literals and as sets of literals interchangeably. To denote the number of literals in a clause A, we use the set notation jAj. A clause A -subsumes a clause B (denoted by A B), if and only if there is a substitution such that A B. If A B and B A, we call A and B -equivalent (written A B). A clause C is -reducible if there exists a clause C0 such that C0 C and jC0j < jCj. A clause with minimal number of literals -equivalent to a clause C is its -reduction. -subsumption corresponds to homomorphism and -reduction corresponds to core of a graph. The Gaifman graph of a clause A is the graph with one vertex for each variable v 2 vars(A) and an edge for every pair of variables u; v 2 vars(A), u 6= v such that u and v appear in a literal l 2 A. The treewidth of a clause is equal to the treewidth of its Gaifman graph. -subsumption and -reduction can be computed in polynomial time for clauses which have bounded-treewidth -reductions.
A clause C is said to be a least general generalization of clauses A and B
(denoted by C 2 LGG(A; B)) if and only if C A, C B and for every clause
D such that D A and D B it holds D C. An LGG of two clauses C,
D can be computed in time O(jCj jDj). LGG can be used as an operator in the
process of searching for hypotheses [
The concept of bounded LGG was introduced in [
Ai for all i 2 f1; :::; ng and if
Ai for all i 2 f1; :::; ng, it holds
Note that neither the clauses to be generalized, nor the resulting bounded LGG
w.r.t. X are required to belong to the set X . In fact, there are cases where we can
show easily that there is no bounded LGG belonging to the set X . The following
example from [
Example 1. Let X = fC1; C2; : : : g be a set of clauses of the following form: C1 =
e(A1; A2), C2 = e(A1; A2) _ e(A2; A3), C3 = e(A1; A2) _ e(A2; A3) _ e(A3; A4),
etc. Let us also have the following two clauses: A = e(X; Y ) _ e(Y; X) and B
= e(X; Y ) _ e(Y; Z) _ e(Z; X). We would like to nd a clause from X which
would be their LGG but this is impossible for the following reason. Any clause
from X -subsumes both A and B but none of them is least general because for
any Ci 2 X we have Ci+1 6 Ci, Ci+1 A and Ci+1 B. On the other hand,
bounded LGG, as actually de ned, always exists which follows trivially from the
fact that the conventional LGG as computed by Plotkin's algorithm [
Notice that the clauses A and B in the above example do not belong to the set X . In fact, one can verify easily that for all the clauses from the set X from the above example, there is always an LGG belonging to the set X . Thus, one might conjecture that, in general, if we restrict the clauses of interest, which we may want to generalize, to be from the set X then we will always be able to nd a bounded LGG from the set X 3. This motivates the de nition of the following, arguably quite natural, type of LGG which is studied in this paper. De nition 2 (LGG in a set X ). Let X be a set of clauses. A clause B 2 X is said to be an LGG of clauses A1, A2, : : : , An 2 X in the set X (denoted by B 2 LGGiXn (A1; A2; : : : ; An)) if and only if B Ai for all i 2 f1; :::; ng and if for every other clause C 2 X such that C Ai for all i 2 f1; :::; ng, it holds C B.
There are several important di erences between LGG in a set X (LGGin ) X and bounded LGG w.r.t. a set X (LGGX ). Most importantly, bounded LGG w.r.t. a set X is not required to belong to the set X which is the property guaranteeing that it always exists. Since LGG in a set X must belong to X , it may be the case that it does not exist. Arguably for the sets X in which LGGiXn exists, it would be preferable over LGGX , especially for the sets X for which tractable -subsumption algorithms exist (e.g. bounded-size or boundedtreewidth clauses). That is one of the reasons why, in this paper, we are interested in the question of existence of LGGin in several such sets of clauses. Here, we note
X that if A1; A2; : : : ; An 2 X and LGG(A1; A2; : : : ; An) 62 X then this does not yet mean that LGGin (A1; A2; : : : ; An) does not exist4.
X 3 Actually, the main negative results presented in this paper show that this is not the case in the majority of interesting cases. 4 If this was the case then the problem of existence of LGGiXn would be almost trivial.
The results of Horvath and Turan [
In this section, to start with a simpler problem before we tackle the question of existence of an LGG operator in the set of bounded-treewidth clauses, we consider the question of existence of LGG in the set of clauses consisting of at most k atoms. We show that there is no LGGiXn operator in the sets of clauses consisting of at most k atoms where k is an integer greater or equal to 4. Theorem 1. If n 4 then there is no LGG operator in the set Xn of clauses with at most n atoms based on one binary predicate. There is an LGG operator in the set X3 of clauses consisting of at most 3 binary atoms with the same predicate.
The next example shows5 that there are clauses A; B 2 X3 such that LGG(A; B)\ X3 = ; and LGGiXn3 (A; B) 6= ;.
Example 2. Let us have the following two clauses: A = e(X; Y ) _ e(Y; X) and B = e(X; Y ) _ e(Y; Z) _ e(Z; X): Their conventional -reduced LGG is LGG(A; B) = e(X1; X2) _ e(X2; X3) _ e(X3; X4) _ e(X4; X5) _ e(X5; X6) _ e(X6; X1); and thus LGG(A; B) \ X3 = ;. However, there exists an LGGiXn3 (A; B), for instance, e(W; X) _ e(X; Y ) _ e(Y; Z) 2 LGGiXn3 (A; B):
Along the same lines, we can show that if we allow more than one binary predicate, the situation becomes even worse.
Theorem 2. If n 3 then there is no LGG operator in the set Xn(2) of clauses with at most n atoms with two di erent binary predicates.
We could see in this section, which was mostly meant to illustrate the general problem of existence of LGGs in sets of clauses, that size of the clauses is not a very good measure for de ning sets of clauses with an LGG operator. This is a bit unfortunate but not very surprising. 5
In this section, we show that there is no LGG in the set of clauses with treewidth 1.
This is quite surprising given the positive result of Horvath and Turan [
Theorem 3. There is no LGG operator for the set of clauses with treewidth 1. Proof. Let us have two clauses
A =red(a1) _ green(a2) _ yellow(a3) _ black(a4) _ e(a5; a1) _ a(a5; a2)_ _ e(a5; a6) _ e(a6; a5) _ e(a6; a3) _ e(a6; a4) _ e(a5; a5) _ e(a6; a6) B =red(b1) _ yellow(b2) _ green(b3) _ black(b4) _ e(b5; b1) _ a(b5; b2)_ _ e(b5; b6) _ e(b6; b5) _ e(b6; b3) _ e(b6; b4) _ e(b5; b5) _ e(b6; b6) The conventional LGG of the clauses A and B is a clause C which represents the graph shown in Figure 1 The clause C is not -reducible (i.e. the corresponding labeled graph is a core) and has treewidth greater than 1 as it contains a clique on 4 vertices. As we have already explained this does not guarantee that there is no LGG of A and B in the set of clauses of treewidth 1. We therefore need to prove that there is indeed no such clause of treewidth 1, which we will do by contradiction.
Let us assume that there is a clause D which is an LGG of A and B and which has treewidth 1. Such a clause must correspond to a labeled tree or forest, possibly with loops. It follows from the de nitions of LGG and LGG in a set that D must also -subsume C. Let us de ne a family of clauses E1 =red(Y1) _ e(X1; Y1) _ e(X1; X2) _ green(Y2) _ e(X2; Y2) _ e(X2; X3)_ _ black(Y3) _ e(X3; Y3) _ e(X3; X4) _ yellow(Y4) _ e(X4; Y4) : : : : : : E2 =red(Y1) _ e(X1; Y1) _ e(X1; X2) _ green(Y2) _ e(X2; Y2) _ e(X2; X3)_ _ black(Y3) _ e(X3; Y3) _ e(X3; X4) _ yellow(Y4) _ e(X4; Y4)_ _ e(X4; X5) _ red(Y5) _ e(X5; Y5) _ _ yellow(X8) _ e(X8; Y8) Ek =red(Y1) _ e(X1; Y1) _ e(X1; X2) _ _ yellow(Y4k) _ e(X4k; Y4k): Clearly, each Ei -subsumes C. By the assumption that D is an LGG in the set of clauses of treewidth 1, each Ei should also -subsume D (because each Ei has treewidth 1 and -subsumes A and B). Let us denote Di = Ei where Ei i D and i is an arbitrary suitable substitution. Since D -subsumes the clause C, no vertex in the graph corresponding to the clause D can be adjacent to two vertices labeled by di erent colors, i.e. the clause D cannot contain simultaneously e.g. literals e(X; Y ), e(X; Z), yellow(Y ) and red(Z). It follows that if e(Xj ; Xj+1) _ e(Xj+1; Xj+2) Ei then i cannot map Xj and Xj+2 on the same term (this follows from the construction of Ei's). For similar reasons, i cannot map Xj and Xj+1 to the same term. Since D corresponds to a directed tree, possibly with loops or cycles of length 2, and therefore contains no simple cycles of length greater than 2, it follows that no two Xj 6= Xj0 can be mapped to the same term in D. However, since D is nite, there must be Ek such that Ek A, Ek B but Ek 6 D which is a contradiction with D being an LGG of A and B in the set of treewidth-1 clauses. It follows that there is no nite LGG of A and B in this set of clauses. tu
Note that the above theorem shows the existence of a counterexample only for treewidth-1 clauses and not for treewidth-k clauses in general. Thus, theoretically, it might be the case that there is an LGG operator in the class of clauses of treewidth at most k, where k > 1, and a proof would still be needed to disprove such a conjecture for general k. This seems unlikely, though. 6
The problems studied in this paper were motivated by the question whether
bounded LGG w.r.t. a set X , introduced in [
Acknowledgement. This work was supported by ERC Starting Grant 240186 \MiGraNT: Mining Graphs and Networks, a Theory-based approach". The rst author is supported by a grant from the Leverhulme Trust (RPG-2014-164).