Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Extended path-indexing

Graf, Peter and Meyer, Christoph

MPI-I-93-253. April 1993, ? pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.

Categories / Keywords: automated deduction, term retrieval, path-indexing
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-93-253.pdfMPI-I-93-253.pdfMPI-I-93-253.dvi - MPI-I-93-253.dvi
111 KBytes; 155 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},