Name
Abstract | ||
|---|---|---|
Indexing data structures have a crucial impact on the performance of automated theorem provers. Examples are discrimination trees, which are like tries where terms are seen as strings and common prefixes are shared, and substitution trees, where terms keep their tree structure and all common contexts can be shared. Here we describe a new indexing data structure, called context trees, where, by means of a limited kind of context variables, common subterms also can be shared, even if they occur below different function symbols. Apart from introducing the concept, we also provide evidence for its practical value. We show how context trees can be implemented by means of abstract machine instructions. Experiments with benchmarks for forward matching show that our implementation is competitive with tightly coded current state-of-the-art implementations of the other main techniques. In particular, space consumption of context trees is significantly less than for other index structures. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1023/B:JARS.0000029963.64213.ac | J. Autom. Reasoning |
Keywords | Field | DocType |
term indexing,automated deduction | Data structure,Computer science,Automated theorem proving,Search engine indexing,Algorithm,Prefix,Theoretical computer science,Tree structure,Weight-balanced tree,Term indexing,Abstract machine | Journal |
Volume | Issue | ISSN |
32 | 2 | 1573-0670 |
Citations | PageRank | References |
6 | 0.62 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Harald Ganzinger | 1 | 1513 | 155.21 |
| Robert Nieuwenhuis | 2 | 1405 | 93.78 |
| Pilar Nivela | 3 | 24 | 4.16 |