Theta-subsumption (θ-subsumption, or just subsumption) is a
decidable relation between two
first-order
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
clauses
In language, a clause is a constituent that comprises a semantic predicand (expressed or not) and a semantic predicate. A typical clause consists of a subject and a syntactic predicate, the latter typically a verb phrase composed of a verb with ...
that guarantees that one clause logically
entails the other. It was first introduced by
John Alan Robinson
John Alan Robinson (9 March 1930 – 5 August 2016) was a philosopher, mathematician, and computer scientist. He was a professor emeritus at Syracuse University.
Alan Robinson's major contribution is to the foundations of automated theorem pr ...
in 1965 and has become a fundamental notion in
inductive logic programming. Deciding whether a given clause θ-subsumes another is an
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
problem.
Definition
A clause, that is, a
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
of first-order
literals, can be considered as a set containing all its disjuncts.
With this convention, a clause
θ-subsumes a clause
if there is a
substitution
Substitution may refer to:
Arts and media
*Chord substitution, in music, swapping one chord for a related one within a chord progression
* Substitution (poetry), a variation in poetic scansion
* "Substitution" (song), a 2009 song by Silversun Pi ...
such that the clause obtained by applying
to
is a subset of
.
Properties
θ-subsumption is a weaker relation than
logical entailment, that is, whenever a clause
θ-subsumes a clause
, then
logically entails
. However, the converse is not true: A clause can logically entail another clause, but not θ-subsume it.
θ-subsumption is decidable; more precisely, the problem of whether one clause θ-subsumes another is NP-complete in the length of the clauses. This is still true when restricting the setting to pairs of
Horn clauses In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the log ...
.
As a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
among Horn clauses, θ-subsumption is
reflexive and
transitive. It therefore defines a
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
. It is not
antisymmetric, since different clauses can be syntactic variants of each other. However, in every
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
of clauses that mutually θ-subsume each other, there is a unique shortest clause up to variable renaming, which can be effectively computed. The class of
quotients with respect to this equivalence relation is a
complete lattice
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
, which has both infinite ascending and infinite descending chains. A subset of this lattice is known as a .
History
θ-subsumption was first introduced by
J. Alan Robinson in 1965 in the context of
resolution
Resolution(s) may refer to:
Common meanings
* Resolution (debate), the statement which is debated in policy debate
* Resolution (law), a written motion adopted by a deliberative body
* New Year's resolution, a commitment that an individual mak ...
, and was first applied to inductive logic programming by
Gordon Plotkin
Gordon David Plotkin, (born 9 September 1946) is a theoretical computer scientist in the School of Informatics at the University of Edinburgh. Plotkin is probably best known for his introduction of structural operational semantics (SOS) and hi ...
in 1970 for finding and reducing least general generalisations of sets of clauses. In 1977, Lewis D. Baxter proves that θ-subsumption is NP-complete, and the 1979 seminal work on NP-complete problems,
Computers and Intractability, includes it among its list of NP-complete problems.
Applications
Theorem provers based on the
resolution
Resolution(s) may refer to:
Common meanings
* Resolution (debate), the statement which is debated in policy debate
* Resolution (law), a written motion adopted by a deliberative body
* New Year's resolution, a commitment that an individual mak ...
or
superposition calculus use θ-subsumption to prune redundant clauses. In addition, θ-subsumption is the most prominent notion of entailment used in
inductive logic programming, where it is the fundamental tool to determine whether one clause is a specialisation or a generalisation of another. It is further used to test whether a clause covers an example, and to determine whether a given pair of clauses is redundant.
Notes
References
*
*
*
*
*
* {{Cite journal , last1=Waldmann , first1=Uwe , last2=Tourret , first2=Sophie , last3=Robillard , first3=Simon , last4=Blanchette , first4=Jasmin , date=November 2022 , title=A Comprehensive Framework for Saturation Theorem Proving , journal=Journal of Automated Reasoning , language=en , volume=66 , issue=4 , pages=499–539 , doi=10.1007/s10817-022-09621-7 , issn=0168-7433 , pmc=9637109 , pmid=36353684
Inductive logic programming
Logical consequence