MPI-I-93-253
Extended path-indexing
Graf, Peter and Meyer, Christoph
April 1993, ? pages.
.
Status: available - back from printing
The performance of a theorem prover crucially depends on the speed of the basic
retrieval operations, such as finding terms that are unifiable with (instances
of, or more general than) some query term. Among the known indexing methods
for term retrieval in deduction systems, Path--Indexing exhibits a good
performance in general. However, as Path--Indexing is not a perfect filter, the
candidates found by this method have still to be subjected to a unification
algorithm in order to detect occur--check failures and indirect clashes.
As perfect filters, discrimination trees and abstraction trees thus
outperform Path--Indexing in some cases. We present an improved version
of Path--Indexing that provides both the query trees and the Path--Index with
indirect clash an occur--check information. Thus compared to the standard
method we dismiss much more terms as possible candidates.
v
Categories / Keywords:
automated deduction, term retrieval, path-indexing
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-253
BibTeX
@TECHREPORT{GrafMeyer93,
AUTHOR = {Graf, Peter and Meyer, Christoph},
TITLE = {Extended path-indexing},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-93-253},
MONTH = {April},
YEAR = {1993},
ISSN = {0946-011X},
}