### On the efficiency of subsumption algorithmsOn the efficiency of subsumption algorithms

Access Restriction
Subscribed

 Author Gottlob, G. ♦ Leitsch, A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1985 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The costs of subsumption algorithms are analyzed by an estimation of the maximal number of unification attempts (worst-case unification complexity) made for deciding whether a clause $\textit{C}$ subsumes a clause $\textit{D}.$ For this purpose the clauses $\textit{C}$ and $\textit{D}$ are characterized by the following parameters: number of variables in $\textit{C},$ number of literals in $\textit{C},$ number of literals in $\textit{D},$ and maximal length of the literals. The worst-case unification complexity immediately yields a lower bound for the worst-case time complexity.First, two well-known algorithms (Chang-Lee, Stillman) are investigated. Both algorithms are shown to have a very high worst-case time complexity. Then, a new subsumption algorithm is defined, which is based on an analysis of the connection between variables and predicates in $\textit{C}.$ An upper bound for the worst-case unification complexity of this algorithm, which is much lower than the lower bounds for the two other algorithms, is derived. Examples in which exponential costs are reduced to polynomial costs are discussed. Finally, the asymptotic growth of the worst-case complexity for all discussed algorithms is shown in a table (for several combinations of the parameters). ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1985-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 32 Issue Number 2 Page Count 16 Starting Page 280 Ending Page 295

#### Open content in new tab

Source: ACM Digital Library