Thumbnail
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

   Open content in new tab
Source: ACM Digital Library