On the efficiency of subsumption algorithms (Q3771609)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4030973
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the efficiency of subsumption algorithms |
scientific article; zbMATH DE number 4030973 |
Statements
On the efficiency of subsumption algorithms (English)
0 references
1985
0 references
unification complexity
0 references
subsumption algorithm
0 references
0.8225462436676025
0 references
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 C subsumes a clause D. For this purpose the clauses C and D are characterized by the following parameters: number of variables in C, number of literals in C, number of literals in 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 analyis of the connection between variables and predicates in 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 table (for several combinations of the parameters).
0 references