Subsumption lattice

A subsumption lattice is a mathematical structure used in the theoretical background of automated theorem proving and other symbolic computation applications.

A term t₁ is said to subsume a term t₂ if a substitution σ exists such that σ applied to t₁ yields t₂. In this case, t₁ is also called more general than t₂, and t₂ is called more specific than t₁, or an instance of t₁.

The set of all (first-order) terms over a given signature can be made a lattice over the partial ordering relation "... is more specific than ..." as follows:

• consider two terms equal if they differ only in their variable naming,^[1]
• add an artificial minimal element Ω (the overspecified term), which is considered to be more specific than any other term.

This lattice is called the subsumption lattice. Two terms are said to be unifiable if their meet differs from Ω.

The join and the meet operation in this lattice are called anti-unification and unification, respectively. A variable x and the artificial element Ω are the top and the bottom element of the lattice, respectively. Each ground term, i.e. each term without variables, is an atom of the lattice. The lattice has infinite descending chains, e.g. x, g(x), g(g(x)), g(g(g(x))), ..., but no infinite ascending ones.

If f is a binary function symbol, g is a unary function symbol, and x and y denote variables, then the terms f(x,y), f(g(x),y), f(g(x),g(y)), f(x,x), and f(g(x),g(x)) form the minimal non-modular lattice N₅ (see Pic. 1); its appearance prevents the subsumption lattice from being modular and hence also from being distributive.

The set of terms unifiable with a given term need not be closed with respect to meet; Pic. 2 shows a counter-example.

Denoting by Gnd(t) the set of all ground instances of a term t, the following properties hold:^[2]

• t equals the join of all members of Gnd(t), modulo renaming,
• t₁ is an instance of t₂ if and only if Gnd(t₁) ⊆ Gnd(t₂),
• terms with the same set of ground instances are equal modulo renaming,
• if t is the meet of t₁ and t₂, then Gnd(t) = Gnd(t₁) ∩ Gnd(t₂),
• if t is the join of t₁ and t₂, then Gnd(t) ⊇ Gnd(t₁) ∪ Gnd(t₂).

The set of linear terms, that is of terms without multiple occurrences of a variable, is a sub-poset of the subsumption lattice, and is itself a lattice. This lattice, too, includes N₅ and the minimal non-distributive lattice M₃ as sublattices (see Pic. 3 and Pic. 4) and is hence not modular, let alone distributive.

The meet operation yields always the same result in the lattice of all terms as in the lattice of linear terms. The join operation in the all terms lattice yields always an instance of the join in the linear terms lattice; for example, the (ground) terms f(a,a) and f(b,b) have the join f(x,x) and f(x,y) in the all terms lattice and in the linear terms lattice, respectively. As the join operations do not in general agree, the linear terms lattice is not properly speaking a sublattice of the all terms lattice.

Join and meet of two proper^[3] linear terms, i.e. their anti-unification and unification, corresponds to intersection and union of their path sets, respectively. Therefore, every sublattice of the lattice of linear terms that does not contain Ω is isomorphic to a set lattice, and hence distributive (see Pic. 5).

Apparently, the subsumption lattice was first investigated by Gordon D. Plotkin, in 1970.^[4]