Least General Generalization

Description:

The procedure least general generalization reads (at least) two clauses as its input and outputs a single clause, implying all input clauses, but being no more general than necessary.

In detail: If c1, c2 and clgg are clauses, with clgg = LGG(c1, c2), then

  • clgg → c1 and clgg → c2, and
  • for every clause cgen, with cgen → c1 and cgen → c2, there exists a substitution θ, such that cgenθ ⊆ clgg.
So there is no clause more specific than clgg, implying c1 and c2. Please follow the link above to "θ-subsumption" to read more about how implication is related to θ-subsumption.

Algebraic properties of the LGG

The least general generalization of clauses is unique up to variable renaming. For all clauses c1, c2 and c3 the following equations hold:

  • LGG(c1, c2) = LGG (c2, c1)
  • LGG( LGG(c1, c2), c3) = LGG( c1, LGG(c2, c3))
  • LGG(c1, c1) = c1

A procedure for finding the lgg of two clauses c1 and c2:

In the first step, all pairs of corresponding literals are grouped together.

If there are literals l1 in clause c1 and l2 in c2,

  • both positive or both negative, and
  • having the same predicate symbol (with the same arity),
then these literals are corresponding. So we have a set of single literals (which do not have a corresponding literal in the other clause) and pairs of literals.

In step 2, for each pair of literals having been grouped together in step 1, the procedure least general generalization for terms is invoked for each component of the literal, and each pair of literals is replaced by the according result. If two terms are replaced, these terms have to be replaced by the same variable each time. Single literals, not having a corresponding literal, are not changed.

The result is the conjunction of all literals from step 2.

Mind that the length of the LGG of clauses can be exponentially large in the length of input clauses, for there can be several pairs of corresponding literals.

To see an example and an applet, demonstrating the least general generalization, please follow the link to the Centre for Computational Learning Systems (CCLS).